[Haskell-cafe] Taking a number to a power and taking its mod
almeidaraf at gmail.com
Sun Jun 15 15:10:26 UTC 2014
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
Calling that funcion with powMod 999999527 2 (999999527-1) is very fast.
What's going on? Can someone shed me some light?
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe