Skip to content

Instantly share code, notes, and snippets.

@trevordixon
Created October 2, 2013 03:00
Show Gist options
  • Save trevordixon/6788535 to your computer and use it in GitHub Desktop.
Save trevordixon/6788535 to your computer and use it in GitHub Desktop.
Modular Exponentiation in Haskell
import Data.Bits
modExp :: Integer -> Integer -> Integer -> Integer
modExp b 0 m = 1
modExp b e m = t * modExp ((b * b) `mod` m) (shiftR e 1) m `mod` m
where t = if testBit e 0 then b `mod` m else 1
@rjy7wb
Copy link

rjy7wb commented Aug 28, 2019

this is bad, a better one is x^y mod n ==

modExp :: Integer -> Integer -> Integer -> Integer
modExp  x y n = mod (x^(mod y (n-1))) (n)
modExp 3 1000 23 = mod (3^(mod 1000 (22))) 23 == mod (3^10) mod 23

@jcsahnwaldt
Copy link

jcsahnwaldt commented Aug 13, 2022

this is bad, a better one is x^y mod n ==

That's a bold statement. And it's misguided. For many (if not most) inputs, @trevordixon's solution is much better.

Let's look at your example:

modExp 3 1000 23 = mod (3^(mod 1000 (22))) 23 == mod (3^10) mod 23

Yes, for this simple example, the simple approach works fine. But watch this:

modExp 3 1000 1023 = mod (3^(mod 1000 (1022))) 23 == mod (3^1000) mod 23

Now the program will actually calculate 3^1000, which has 478 decimal digits, and then it will take the mod 23 of that huge number, which produces a two-digit number. Quite a waste of time and space. @trevordixon's solution never produces such huge intermediate results.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment