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

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.