Modular Exponentiation in Haskell

modExp.hs

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

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

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.

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

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.