I am trying to understand why the modular exponentiation algorithm has a running time of about $\log(n)$ where $n$ is the exponent. Here is the algorithm:
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 think it has something to do with the number of bits for the binary representation of the exponent. What is also an intuitive numerical example?