Problem Detail: 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?
Asked By : CodeKingPlusPlus
Answered By : Ran G.
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=acdot a$, then $a^4=a^2cdot 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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7446
