Repeated squaring algorithm

In preparation for computing with Fermat's little theorem and Euler's theorem, both of which will be stated later, we show how to efficiently compute the power of an integer modulo $m$.

One way to compute $a^n$ modulo $m$ is simply to compte $a^n$ then to reduce modulo $m$. This is relatively hard to do if $n$ is large since there are a lot of digits to keep track of. An alternative method is given below.

Repeated squaring algorithm

To compute $a^n$ modulo $m$:

step 1: write $n$ is binary,

$$n=a_k2^k+...+a_12+a_0,$$

where each $a_i$ is either 0 or $1$.

step 2: Compute

$$a \ ({\rm mod}\ m),\ a^{ 2} \ ({\rm mod}\ m),\ ..., a^{2^k} \ ({\rm mod}\ m),$$

(in that order).

step 3: Compute $a^n=a^{a_0}a^{a_1 2}... a^{a_k2^k}\ ({\rm mod}\ m)$.

Example 1.7.8   We compute $10^{11}\ ({\rm mod}\ 21)$. First, $11=8+2+1$, so we compute

• $10\ ({\rm mod}\ 21)=10$,
• $10^2\ ({\rm mod}\ 21)=16$,
• $10^4\ ({\rm mod}\ 21)=16^2=4$,
• $10^8\ ({\rm mod}\ 21)=4^2=16$.

Thus $10^{11}\ ({\rm mod}\ 21)=4\cdot 16\cdot 10=19$.