Exponentiation by squaring

Question

While i was searching for Exponentiation by squaring i got the recursive method there but then i stumbled upon this pseudo code , Which i'm unable to understand fully.

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
} 

if you can give some insight in simple terms it will be of great help

Answer 1

The code relies on the fact that:

x^y == (x*x)^(y/2)

The loop is doing exactly that: dividing the exponent by two while squaring the base.

An example:

Let's consider computing the result of 3^13. You can write the exponent (13) as a sum of binary powers: 3^(8+4+1). Then: 3^13 = 3^8 * 3^4 * 3^1.

This decomposition in binary powers is done by the %2, /2 done in the code, using the rationale exponained above.

Step by step:

You start with 3^13. As 13%2==1, you multiply the result by 3, because the answer does have a factor 3^1.

Then you divide the exponent by 2 and square the base (9^6 == 3^12). As 6%2==0, this means the answer doesn't have a factor 3^2.

Then you divide the exponent by 2 and square the base (81^3 == 3^12). As 3%2==1, you multiply the result by 81 because the answer does have a factor 3^4.

Then you divide the exponent by 2 and square the base (6561^1 == 3^8). As 1%2==1, you multiply the result by 6561 because the answer does have a factor 3^8.

Answer 2

Assume you want to calculate x^y with y in Z. Note y=y/2+y%2 (using "/" as integer division an "%" as modulus).

a) if y == 0 then x^y=1; if y==1 then x^y=x; if y==-1 then x^y=1/x.

b) If y%2 == 0 then x^y = (x^2)^(y/2) => square x (x'=x^2), divide y by two (y'=y/2), and apply recursively the algorithm to calculate x'^y' = x^y.

c) If y%2 == 1 then x^y = (x^2)*((x^2)^(y/2)) => square x (x'=x^2), divide y by two (y'=y/2), and apply recursively the algorithm to calculate x'^y', and after x^y = x'*(x'^y').

In this way, using only integer division and square of values you can calculate any exponential.

Example: x^19

1) 19%2==1 [rule c] => x^19=x'*(x'^9) where x' = x^2.
2) 9%2==1 [rule c] => x'^9=x''*(x''^4) where x'' = x'^2.
3) 4%2==0 [rule b] => x''^4=x'''^2 where x''' = x''^2.
4) 2%2==0 [rule b] => x'''^2 = x''''^1 where x''''=x'''^2.
5) x''''^1 [rule a] is immediate.

if the calculus is done over a finite field of integers mod n, the logic is the same.

Addendum

In fact, same logic can be used to the more simple calculus and more easy to understand problem of a number multiplied by an integer: x*y.

a) if y == 0 then x*y=0; if y==1 then x*y=x; if y==-1 then x*y=-x.

b) If y%2 == 0 then x*y = (x*2)*(y/2) => multiply x by 2 (x'=x*2), divide y by two (y'=y/2), and apply recursively the algorithm to calculate x'*y' = x*y.

c) If y%2 == 1 then x*y = (x*2)+(x*2)*(y/2) => multiply x (x'=x*2), divide y by two (y'=y/2), apply recursively the algorithm to calculate x'*y', and after x*y = x'+x'*y'.

int way, product is reduced to addition and shift operations.