How to Compute $a^m\pmod{n}$

Let $a$ and $n$ be integers, and $m$ a nonnegative integer. In this section we describe an efficient algorithm to compute $a^m\pmod{n}$ . For the cryptography applications in Chapter 3, $m$ will have hundreds of digits.

The naive approach to computing $a^m\pmod{n}$ is to simply compute $a^m = a\cdot a \cdots a\pmod{n}$ by repeatedly multiplying by $a$ and reducing modulo $m$ . Note that after each arithmetic operation is completed, we reduce the result modulo $n$ so that the sizes of the numbers involved do not get too large. Nonetheless, this algorithm is horribly inefficient because it takes $m-1$ multiplications, which is huge if $m$ has hundreds of digits.

A much more efficient algorithm for computing $a^m\pmod{n}$ involves writing $m$ in binary, then expressing $a^m$ as a product of expressions $a^{2^i}$ , for various $i$ . These latter expressions can be computed by repeatedly squaring $a^{2^i}$ . This more clever algorithm is not ``simpler'', but it is vastly more efficient since the number of operations needed grows with the number of binary digits of $m$ , whereas with the naive algorithm above the number of operations is $m-1$ .

Algorithm 2.3 (Write a number in binary)   Let $m$ be a nonnegative integer. This algorithm writes $m$ in binary, so it finds $\varepsilon _i\in\{0,1\}$ such that $m=\sum_{i=0}^r \varepsilon _i 2^i$ with each $\varepsilon _i\in\{0,1\}$ .

1. [Initialize] Set $i=0$ .
2. [Finished?] If $m=0$ , terminate.
3. [Digit] If $m$ is odd, set $\varepsilon _i=1$ , otherwise $\varepsilon _i=0$ . Increment $i$ .
4. [Divide by $2$ ] Set  $m =\left\lfloor\frac{m}{2}\right\rfloor$ , the greatest integer $\leq m/2$ . Goto step 2.

SAGE Example 2.3   To write a number in binary using SAGE, use the str command:

sage: 100.str(2)
'1100100'

Notice the above is the correct binary expansion:

sage: 0*2^0 + 0*2^1 + 1*2^2 + 0*2^3 + 0*2^4 + 1*2^5 + 1*2^6
100

Algorithm 2.3 (Compute Power)   Let $a$ and $n$ be integers and $m$ a nonnegative integer. This algorithm computes $a^m$ modulo $n$ .

1. [Write in Binary] Write $m$ in binary using Algorithm 2.3.11, so $a^m = \prod_{\varepsilon _i = 1} a^{2^i}\pmod{n}.$
2. [Compute Powers] Compute $a$ , $a^2$ , $a^{2^2} = (a^2)^2$ , $a^{2^3} = (a^{2^2})^2$ , etc., up to $a^{2^r}$ , where $r+1$ is the number of binary digits of $m$ .
3. [Multiply Powers] Multiply together the $a^{2^i}$ such that $\varepsilon _i=1$ , always working modulo $n$ .

Example 2.3   We can compute the last $2$ digits of $7^{91}$ , by finding $7^{91}\pmod{100}$ . First, because $\gcd(7,100)=1$ , we have by Theorem 2.1.19 that $7^{\varphi (100)} \equiv 1\pmod{100}$ . Because $\varphi$ is multiplicative,

$$\varphi (100) = \varphi (2^2\cdot 5^2) = (2^2-2)\cdot(5^2-5)=40.$$

Thus $7^{40} \equiv 1\pmod{100}$ , hence

$$7^{91} \equiv 7^{40 + 40 + 11} \equiv 7^{11} \pmod{100}.$$

We now compute $7^{11}\pmod{100}$ using the above algorithm. First, write $11$ in binary by repeatedly dividing by $2$ .

$$11 = 5\cdot 2 + 1$$

$$5 = 2\cdot 2 + 1$$

$$2 = 1\cdot 2 + 0$$

$$1 = 0\cdot 2 + 1$$

So in binary, $(11)_2 = 1011$ , which we check:

$$11 = 1\cdot8 + 1\cdot2 + 1.$$

Next, compute $a, a^2, a^4, a^8$ and output $a^8 \cdot a^2 \cdot a$ . We have

$$a = 7$$

$$a^2 \equiv 49$$

$$a^4 \equiv 49^2 \equiv 1$$

$$a^8 \equiv 1^2 \equiv 1$$

Note - it is easiest to square $49$ by working modulo $4$ and $25$ and using the Chinese Remainder Theorem. Finally,

$$7^{91} \equiv 7^{11} \equiv a^8 \cdot a^2 \cdot a \equiv 1 \cdot 49 \cdot 7 \equiv 43 \pmod{100}.$$

SAGE Example 2.3   SAGE implements the above algorithm for computing powers efficiently. For example,

sage: Mod(7,100)^91
43

We can also, of course, directly compute $7^{91}$ in SAGE, though we would not want to do this by hand:

sage: 7^91
80153343160247310515380886994816022539378033762994852007501964604841680190743