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?

  • $\begingroup$ 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? $\endgroup$ – 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$.

  • 1
    $\begingroup$ 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. $\endgroup$ – jww Jun 14 '15 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.