{"id":2287,"date":"2016-04-06T05:00:18","date_gmt":"2016-04-06T03:00:18","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2287"},"modified":"2022-03-26T12:11:57","modified_gmt":"2022-03-26T10:11:57","slug":"inverso-multiplicativo-modular","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/inverso-multiplicativo-modular\/","title":{"rendered":"Inverso multiplicativo modular"},"content":{"rendered":"<p>El <a href=\"http:\/\/bit.ly\/1TvmSED\">inverso multiplicativo modular<\/a> de un entero n m\u00f3dulo p es el n\u00famero m, entre 1 y p-1, tal que<\/p>\n<pre lang=\"text\">\n   mn = 1 (mod p)\n<\/pre>\n<p>Por ejemplo, el inverso multiplicativo de 2 m\u00f3dulo 5 es 3, ya que 1 &lt;= 3 &lt;= 4 y 2&#215;3 = 1 (mod 5).<\/p>\n<p>El inverso multipicativo de n m\u00f3dulo p existe si y s\u00f3lo si n y p son coprimos; es decir, si mcd(n,p) = 1.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   invMod :: Integer -> Integer -> Maybe Integer\n<\/pre>\n<p>tal que (invMod n p) es justo el inverso multiplicativo de n m\u00f3dulo p, si existe y Nothing en caso contrario. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> invMod 2 5\n   Just 3\n   \u03bb> invMod 2 6\n   Nothing\n   \u03bb> [(x,invMod x 5) | x <- [0..4]]\n   [(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)]\n   \u03bb> [(x,invMod x 6) | x <- [0..5]]\n   [(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)]\n   \u03bb> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)\n   True\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n-- 1\u00aa definici\u00f3n\n-- =============\n\ninvMod1 :: Integer -> Integer -> Maybe Integer\ninvMod1 n p | gcd n p == 1 = Just (head [m | m <- [1..p-1], m*n `mod` p == 1])\n            | otherwise    = Nothing\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\ninvMod2 :: Integer -> Integer -> Maybe Integer\ninvMod2 n p | m \/= 1    = Nothing\n            | x < 0     = Just (x + p)\n            | otherwise = Just x\n    where (x,_,m) = mcdExt n p\n\n-- [Algoritmo extendido de Euclides]\n-- (mcd a b) es la terna (x,y,g) tal que g es el m\u00e1ximo com\u00fan divisor\n-- de a y b y se cumple que ax + by = g. Por ejemplo,\n--    mcdExt  2  5  ==  (-2,1,1)\n--    mcdExt  2  6  ==  ( 1,0,2)\n--    mcdExt 12 15  ==  (-1,1,3)\nmcdExt :: Integer -> Integer -> (Integer,Integer,Integer)\nmcdExt a 0 = (1, 0, a)\nmcdExt a b = (t, s - q * t, g)\n  where (q, r)    = a `quotRem` b\n        (s, t, g) = mcdExt b r\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\ninvMod3 :: Integer -> Integer -> Maybe Integer\ninvMod3 n p | gcd n p == 1 = Just (aux n p)\n            | otherwise    = Nothing\n  where aux 1 p = 1\n        aux n p = (x * p + 1) `div` n\n          where x = n - aux (p `mod` n) n                    \n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> invMod1 (10^7) (1+10^7)\n--    Just 10000000\n--    (5.05 secs, 2,872,350,896 bytes)\n--    \u03bb> invMod2 (10^7) (1+10^7)\n--    Just 10000000\n--    (0.00 secs, 0 bytes)\n--    \u03bb> invMod3 (10^7) (1+10^7)\n--    Just 10000000\n--    (0.00 secs, 0 bytes)\n--    \n--    \u03bb> let n = 10^7 in invMod2 (10^n) (1+10^n) == Just (10^n)\n--    True\n--    (0.88 secs, 55,728,120 bytes)\n--    \u03bb> let n = 10^7 in invMod3 (10^n) (1+10^n) == Just (10^n)\n--    True\n--    (1.99 secs, 80,644,352 bytes)\n<\/pre>\n<h4>Soluci\u00f3n en Maxima<\/h4>\n<pre lang=\"text\">\ninvMod (n,p) := block ([r],\n  r : inv_mod (n,p),\n  if integerp (r)\n  then Just (r)\n  else Nothing)$\n<\/pre>\n<p>La evaluaci\u00f3n de los ejemplos es<\/p>\n<pre lang=\"text\">\n(%i2) invMod (2,5);\n(%o2) Just(3)\n(%i3) invMod (2,6);\n(%o3) Nothing\n(%i4) makelist([x,invMod(x,5)],x,0,4);\n(%o4) [[0,Nothing],[1,Just(1)],[2,Just(3)],[3,Just(2)],[4,Just(4)]]\n(%i5) makelist([x,invMod(x,6)],x,0,5);\n(%o5) [[0,Nothing],[1,Just(1)],[2,Nothing],[3,Nothing],[4,Nothing],[5,Just(5)]]\n(%i6) (n : 10^7, is (invMod (10^n,1+10^n) = Just (10^n)));\n(%o6) true\n<\/pre>\n<h4>Referencia<\/h4>\n<ul>\n<li><a href=\"http:\/\/bit.ly\/1SwpWLL\">Calculating multiplicative inverses in modular arithmetic<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>El inverso multiplicativo modular de un entero n m\u00f3dulo p es el n\u00famero m, entre 1 y p-1, tal que mn = 1 (mod p) Por ejemplo, el inverso multiplicativo de 2 m\u00f3dulo 5 es 3, ya que 1 &lt;= 3 &lt;= 4 y 2&#215;3 = 1 (mod 5). El inverso multipicativo de n m\u00f3dulo&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[8,500,155,71,89,254,6],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2287"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=2287"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2287\/revisions"}],"predecessor-version":[{"id":2321,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2287\/revisions\/2321"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2287"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}