[Haskell-cafe] Taking a number to a power and taking its mod

[Rafael Almeida]

Hello,

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140615/2b387f55/attachment.html>