Repeated squaring algorithm

How hard do you think it would be to compute by hand $2^{128} {\rm mod} 5$ ? If you guess too hard, you're wrong. The algorithm described below shows how such seemingly difficult calculations are actually quite easy. 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. We describe an alternative method.

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