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
1 |
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
1 |
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,
1 2 3 4 5 6 7 8 9 10 |
λ> 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
-- 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
1 2 3 4 5 |
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
1 2 3 4 5 6 7 8 9 10 |
(%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 |
Solución en Maxima (la funcion invMod ya está definida, y además con el mismo nombre):