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?