Exponentiation

Now we may ask ourselves: How fast can we do these modular arithmetic operations? When we multiply two $n$-digit numbers, it is easy to see that a school multiplication method would give us $O(n^2)$ bit operations. But what about exponentiation? In particular, how fast can we compute $a^b \pmod{m}$? If we do multiplications $a \cdot a \ldots \cdot a$ ($b$ times), this would require $O(b n^2)$ bit operations which is inefficient (recall that the encoding length of $b$ is only $O(\log b)$, so this running time is exponential in the size of the input). We can do much better with the method of repeated squaring.

$\mathrm{Mod-Exp}(a,b,m)$

1. $X \leftarrow 1$, $B\leftarrow b$, $A \leftarrow a \pmod{m}$
2. while $B \geq 1$ do
   1. if $B$ is odd, then $B \leftarrow B-1$, $X\leftarrow A X \pmod{m}$
   2. else $B \leftarrow B/2$, $A\leftarrow A^2 \pmod{m}$
3. return $X$

Exercise 45

Prove that the following is loop invariant:

$X A^B = a^b \pmod{m}$

From the above exercise and the fact that the initialized value satisfies the loop invariant's condition, we know that the condition must hold at the end of the algorithm, which has $B=0$. Therefore, $X = a^b \pmod{m}$ and the returned value is correct. The running time analysis follows from the following exercise:

Exercise 46

After every two rounds, the value of $B$ is reduced to less than half.

This implies that if $B$ originally has $n$ bits, the number of rounds would be at most $2n$. Each round only involves basic multiplications (with complexity $O(n^2)$). Therefore, the total running time of this algorithm is $O(n^3)$.¹

Footnotes

1. Note that, to simplify the analysis, in this section we assumed that the number of bits of $a$, $b$ and $m$ is $n$. ↩