Interesting. I had a read on this wikipedia article as well: http://en.wikipedia.org/wiki/Modular_exponentiation

It gives us one important theorem: a*b `mod` m == (a*(b `mod` m)) `mod` m

That's what makes exponentiation by squaring so appealing. I wrote the function in a way that I found it easier to understand. Take a look:

powMod :: Integral a => a -> a -> a -> a
powMod _ _ 0 = 1 
powMod m x 1 = x `mod` m
powMod m x n 
    | even n = powMod m modSquare (n`div`2)
    | otherwise = (x * powMod m modSquare ((n-1)`div`2)) `mod` m
    where modSquare = x * (x `mod` m)

That funcion does the pow-mod operation much quickier than doing n^k `mod` m. Unfortunately, nothing of those things actually solved the prime1 SPOJ problem :P

I mostly gave it up, already. I liked learning those things, though :)

On Sun, Jun 15, 2014 at 12:34 PM, Herbert Valerio Riedel <hvr@gnu.org> wrote:
Hello Rafael,

On 2014-06-15 at 17:10:26 +0200, Rafael Almeida wrote:

[...]

> 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?

One of the reason that powMod is very fast is because it avoids
allocating large integer bignums by

  http://en.wikipedia.org/wiki/Exponentiation_by_squaring


Just for the record (should you want an even more optimized powMod
implementation): integer-gmp now exposes a few highly optimized Integer
primitives, including a powMod:

  http://hackage.haskell.org/package/integer-gmp-0.5.1.0/docs/GHC-Integer-GMP-Internals.html#v:powModInteger


HTH,
  hvr