Explanation of right to left binary method of modu

问题:

I have been studying this link from wikipedia of modulo of a large number, Here is the pseudocode.

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

I don't understand the explanation given in wiki.Why I have to check if exp%2 is even or odd. also why I am doing the three operations?

回答1:

This algorithm is a combination of the Exponentiation by Squaring algorithm and modulo arithmetic.

To understand what's going on, first consider a situation when exponent is a power of 2. Then, assuming that exponent = 2 ^ k, the result could be computed by squaring the result k times, i.e.

res = (...((base ^ 2) ^2 ) ... ) ^2))
              ---------------------
                     k times

When exponent is not a power of 2, we need to make additional multiplications. It turns out that if we can divide exponent by 2 without remainder, we can square the base, and divide the exponent. If, however, there is a remainder, we must additionally multiply the intermediate result by the value of the current base.

What you see is the same exponentiation by squaring applied to modulo multiplication. The algorithm denotes integer division by two using the exponent >> 1 operation, which is identical to floor(exponent / 2).