Menu Close

Inverso multiplicativo modular

El inverso multiplicativo modular de un entero n módulo p es el número m, entre 1 y p-1, tal que

   mn = 1 (mod p)

Por ejemplo, el inverso multiplicativo de 2 módulo 5 es 3, ya que 1 <= 3 <= 4 y 2×3 = 1 (mod 5).

El inverso multipicativo de n módulo p existe si y sólo si n y p son coprimos; es decir, si mcd(n,p) = 1.

Definir la función

   invMod :: Integer -> Integer -> Maybe Integer

tal que (invMod n p) es justo el inverso multiplicativo de n módulo p, si existe y Nothing en caso contrario. Por ejemplo,

   λ> invMod 2 5
   Just 3
   λ> invMod 2 6
   Nothing
   λ> [(x,invMod x 5) | x <- [0..4]]
   [(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)]
   λ> [(x,invMod x 6) | x <- [0..5]]
   [(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)]
   λ> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)
   True

Soluciones

-- 1ª definición
-- =============
 
invMod1 :: Integer -> Integer -> Maybe Integer
invMod1 n p | gcd n p == 1 = Just (head [m | m <- [1..p-1], m*n `mod` p == 1])
            | otherwise    = Nothing
 
-- 2ª definición
-- =============
 
invMod2 :: Integer -> Integer -> Maybe Integer
invMod2 n p | m /= 1    = Nothing
            | x < 0     = Just (x + p)
            | otherwise = Just x
    where (x,_,m) = mcdExt n p
 
-- [Algoritmo extendido de Euclides]
-- (mcd a b) es la terna (x,y,g) tal que g es el máximo común divisor
-- de a y b y se cumple que ax + by = g. Por ejemplo,
--    mcdExt  2  5  ==  (-2,1,1)
--    mcdExt  2  6  ==  ( 1,0,2)
--    mcdExt 12 15  ==  (-1,1,3)
mcdExt :: Integer -> Integer -> (Integer,Integer,Integer)
mcdExt a 0 = (1, 0, a)
mcdExt a b = (t, s - q * t, g)
  where (q, r)    = a `quotRem` b
        (s, t, g) = mcdExt b r
 
-- 3ª definición
-- =============
 
invMod3 :: Integer -> Integer -> Maybe Integer
invMod3 n p | gcd n p == 1 = Just (aux n p)
            | otherwise    = Nothing
  where aux 1 p = 1
        aux n p = (x * p + 1) `div` n
          where x = n - aux (p `mod` n) n                    
 
-- Comparación de eficiencia
-- =========================
 
--    λ> invMod1 (10^7) (1+10^7)
--    Just 10000000
--    (5.05 secs, 2,872,350,896 bytes)
--    λ> invMod2 (10^7) (1+10^7)
--    Just 10000000
--    (0.00 secs, 0 bytes)
--    λ> invMod3 (10^7) (1+10^7)
--    Just 10000000
--    (0.00 secs, 0 bytes)
--    
--    λ> let n = 10^7 in invMod2 (10^n) (1+10^n) == Just (10^n)
--    True
--    (0.88 secs, 55,728,120 bytes)
--    λ> let n = 10^7 in invMod3 (10^n) (1+10^n) == Just (10^n)
--    True
--    (1.99 secs, 80,644,352 bytes)

Solución en Maxima

invMod (n,p) := block ([r],
  r : inv_mod (n,p),
  if integerp (r)
  then Just (r)
  else Nothing)$

La evaluación de los ejemplos es

(%i2) invMod (2,5);
(%o2) Just(3)
(%i3) invMod (2,6);
(%o3) Nothing
(%i4) makelist([x,invMod(x,5)],x,0,4);
(%o4) [[0,Nothing],[1,Just(1)],[2,Just(3)],[3,Just(2)],[4,Just(4)]]
(%i5) makelist([x,invMod(x,6)],x,0,5);
(%o5) [[0,Nothing],[1,Just(1)],[2,Nothing],[3,Nothing],[4,Nothing],[5,Just(5)]]
(%i6) (n : 10^7, is (invMod (10^n,1+10^n) = Just (10^n)));
(%o6) true

Referencia

7 soluciones de “Inverso multiplicativo modular

  1. anaagusil
     
    -- Es poco eficiente 
     
    coprimos :: Integral a => a -> a -> Bool
    coprimos p n = mod p n == 1
     
    invMod' :: Integral t => Integer -> Integer -> [Integer]
    invMod' x n = [ y | y <- [1..n], coprimos (x*y) n ]
     
    invMod :: Integer -> Integer -> Maybe Integer
    invMod x n | invMod' x n == [] = Nothing
               | otherwise         = Just (head (invMod' x n))
  2. manpende
    invMod :: Integer -> Integer -> Maybe Integer
    invMod n p | gcd n p == 1 = invModAux 1 n p
               | otherwise = Nothing
     
    invModAux :: Integer -> Integer -> Integer -> Maybe Integer
    invModAux m n p | rem (m*n) p == 1 = Just m
                    | otherwise = invModAux (m+1) n p
  3. fracruzam
    invMod (n,p) := block([m : 1, r : Nothing],
      if gcd(n,p) = 1
           then ( unless mod(m*n,p) = 1
                  do ( m : m + 1),
                  r : Just(m)),
                r)$
     
    /* (%i33) f(x) := [x,invMod(x,5)]$
       (%i34) makelist(f(x),x,0,4);
       (%o34) [[0, Nothing], [1, Just(1)], [2, Just(3)], [3, Just(2)],
               [4, Just(4)]]
       (%i35) f(x) := [x,invMod(x,6)]$
       (%i36) makelist(f(x),x,0,5);
       (%o36) [[0, Nothing], [1, Just(1)], [2, Nothing], [3, Nothing],
               [4, Nothing],5, Just(5)]] */
  4. alvalvdom1
    invMod :: Integer -> Integer -> Maybe Integer
    invMod n p | gcd n p == 1 = Just (head [x | x <- [1..p-1], mod (x*n) p == 1])
               | otherwise = Nothing
  5. manvermor
    -- Función pedida:
     
    invMod :: Integer -> Integer -> Maybe Integer
    invMod n p | gcd n p == 1 = Just $ mod (fst $ (bezout n p)) p
               | otherwise = Nothing
     
    -- Para ello definimos la "Identidad de Bezout" mediante un par (x,y)
    -- que cumple que mcd (a,b) = x*a + y*b, donde la componente x es el
    -- inverso multiplicativo de a.
     
    bezout :: Integer -> Integer -> (Integer, Integer)
    bezout _ 0 = (1,0)
    bezout _ 1 = (0,1)
    bezout a b = (b',a' - q*b')
         where (a',b') = bezout b r
               (q,r) = quotRem a b
     
    -- *Main> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)
    -- True
    -- (14.09 secs, 57,753,688 bytes)
  6. juamorrom1
    -- Sin usar usar la función "mod".
    invMod :: Integer -> Integer -> Maybe Integer
    invMod n p | gcd n p == 1 = Just $ (multiploDeN [n,2*n..] ps) `div` n
               | p == n+1     = Just p
               | otherwise    = Nothing
            where ps = 1:[p+1,(2*p)+1..]
     
    multiploDeN :: Ord a => [a] -> [a] -> a
    multiploDeN (x:xs) ys | elem x (takeWhile (<=x) ys) = x
                          | otherwise = multiploDeN xs ys
  7. abrdelrod

    Solución en Maxima (la funcion invMod ya está definida, y además con el mismo nombre):

    invMod (n,p) := if gcd (n,p) = 1 then Just (inv_mod (n,p)) else Nothing$

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.