Modular exponentiation: Difference between revisions

Content added Content deleted

Inline

@@ Line 876: / Line 876: @@
 =={{header|Haskell}}==
+<lang haskell>
-<lang haskell>powm :: Integer -> Integer -> Integer -> Integer -> Integer
+modPow :: Integer -> Integer -> Integer -> Integer -> Integer
-powm b 0 m r = r
-powm b e m r
+modPow b e 1 r = 0
+modPow b 0 m r = r
-  | e `mod` 2 == 1 = powm (b * b `mod` m) (e `div` 2) m (r * b `mod` m)
+modPow b e m r
-powm b e m r = powm (b * b `mod` m) (e `div` 2) m r
+  | e `mod` 2 == 1 = modPow b' e' m (r * b `mod` m)
+  | otherwise = modPow b' e' m r
+  where
+    b' = b * b `mod` m
+    e' = e `div` 2
-main :: IO ()
+main = do
+  print (modPow 2988348162058574136915891421498819466320163312926952423791023078876139
-main =
-  print $
-  powm
-    2988348162058574136915891421498819466320163312926952423791023078876139
     2351399303373464486466122544523690094744975233415544072992656881240319
     (10 ^ 40)
-</lang>
+)
+</lang>
 {{out}}
 <pre>1527229998585248450016808958343740453059</pre>