Explanation of the right to the left binary modular arithmetic method?

Question

I am studying this link from Wikipedia modulo a large number. Here is the pseudo code.

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 the wiki.Why, I have to check if exp% 2 is even or odd. also why am i doing three operations?

Answer 1

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

, , , exponent 2. , , exponent = 2 ^ k, k , ..

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

exponent 2, . , exponent 2 , . , , , base.

, , - , , . , exponent >> 1, floor(exponent / 2).