I've been trying to do a problem from SPOJ which requires me to find prime numbers in a range. I've been battling with several possibility, so far I have had no luck. I remember primality tests from college. So I looked up the one I knew: fermat's little theorem. It requires me to do this check:

    a^(p-1) `mod` p == 1

However, taking a number to a large power is very slow. So it was even worse than the solution I was already trying.

I'm not here for your guys to give me the solution. But I'm here to understand how can I do that operation quickly. This wiki entry implements powMod

    http://www.haskell.org/haskellwiki/Testing_primality

Calling that funcion with powMod 999999527 2 (999999527-1) is very fast. What's going on? Can someone shed me some light?

[]'s

Rafael