# Running Time of Modular Exponentiation

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?

-

## migrated from cstheory.stackexchange.comDec 16 '12 at 19:47

This question came from our site for theoretical computer scientists and researchers in related fields.

I suggest you try this algorithm on some small $n$, and try to see what's going on. This way you will provide the "intuitive numerical example" yourself. Regarding your first question, can you tell from $n$ how many times the loop will run? – Yuval Filmus Dec 16 '12 at 20:03

The main idea is that $a^x \cdot a^x = a^{2x}$.
Now, in order to get, say, $a^{10}$ you can do $res = res * a$ for 10 times. On the other hand you can do compute $a^2=a\cdot a$, then $a^4=a^2\cdot a^2$, then $a^8 = a^4 \cdot a^4$, and get the final result by multiplying $a^8$ with $a^2$. That is, we "break" the computation in a similar way to the binary representation of the exponent.
Let me give do the example in more details, and then give the general statement. note that $10 = 1010_{(2)}$, and can think of each '1' bit as an element we need to multiply in order to get the final answer (here $a^8$ for the 4th bit, and $a^2$ for the 2nd lsb bit. The power is the same as the "value" of that bit in binary..).
Generaly, in order to compute $a^{exp}$, consider $exp_{(2)}$: the MSB is always 1, and you will have to compute the element $a^{2^{\lfloor \log exp \rfloor}}$, which will take you $\log exp$ (modular) multiplications, and generate $a^2, a^4, a^8, a^{16}, ..., a^{2^{\lfloor \log exp \rfloor}}$. Finally, with another up to $\log exp$ multiplication you will multiply all the elements that correspond to a '1' bit in the binary representation of $exp$.
I think the non-intuitive point is the cost of the multiplication is discarded. A modular multiplication costs $O(m * log(n))$, so it seems like a modular exponentiation should cost $O(log(exp) * m * log(n))$ or similar. – jww Jun 14 '15 at 23:23