Finding find a^s mod b

Question

We are given 3 numbers: a,s and b, each varying in the range between 1 and 1000000. We need to find pow(a,s)%b. Obviously, we can not use the simple pow function because we could not generate big number such as 1000000^1000000. This is the solution of the problem:

sol=1
for(int i=0;i<s;i++) 
{
            sol = sol * a;
            sol = sol % b;
}

print sol

I don't understand this algorithm. Can someone explain it to me?

P.S. Where can I find more algorithms for solving non-trivialc math problems such as this one? Cheers!

Answer 1

First of all, the algorithm you wrote is not at all optimized, since it's linear in s, while you can easily write a log(s) one, as you can read here.

That said, there isn't much to explain: you just have to know that

a*b mod N = ((a mod N) * ( b mod N)) mod N

and that

a^s = a*a*...*a s times

and it immediately follows that your algorithm computes the result in the naive way.

Answer 2

a^s mod b = (a • a^s-1) mod b = (a mod b) • (a^s-1 mod b) mod b = ...

As you can see the first step is trivial, while the second step is a known property of modulo. So you can iterate and find a^s mod b.

As other mentioned you can do better. For the other method you can go to Wikipedia. But I will explain the idea behind this algorithm: Represent the number s in binary so you can write s in the following way:

s=∑(2ⁱ • b_i) where each b_i is 0 or 1.

So: a^s mod b = a^{∑(2i • b_i)} mod b, so you can just do the multiplication when the LSB = 1 then shift right the exponent ...