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
@Shihab-Shahriar
Copy link

Bloody Hell...This Is unbelievably first. Would you please explain?

@Xaltonon
Copy link

Xaltonon commented Jul 10, 2017

It's exponentiation by squaring. Also, by applying modulo after every multiplication, it never needs to deal with numbers greater than m. Also see modular exponentiation on Wikipedia.

@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