Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

migrated from cstheory.stackexchange.com Dec 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
add comment

1 Answer 1

up vote 4 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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