Throughout this book, we will be interested in numbers of the form

In this and the next couple of sections, we discuss some properties of numbers raised to a power modulo an integer.

Suppose we want to compute $2^{1234}(\text{mod}789)\text{.}$ If we first compute $2^{1234}\text{,}$ then reduce mod 789, we’ll be working with very large numbers, even though the final answer has only 3 digits. We should therefore perform each multiplication and then calculate the remainder. Calculating the consecutive powers of 2 would require that we perform the modular multiplication 1233 times. This is method is too slow to be practical, especially when the exponent becomes very large. A more efficient way is the following (all congruences are mod 789).

We start with $2^2\equiv 4(\text{mod}789)$ and repeatedly square both sides to obtain the following congruences:

Since $1234=1024+128+64+16+2$ (this just means that 1234 equals 10011010010 in binary), we have

Note that we never needed to work with a number larger than ${788}^2\text{.}$

The same method works in general. If we want to compute $a^b(\text{mod}n)\text{,}$ we can do it with at most $2{log}_2(b)$ multiplications mod $n\text{,}$ and we never have to work with numbers larger than $n^2\text{.}$ This means that exponentiation can be accomplished quickly, and not much memory is needed.

This method is very useful if $a\text{,}b\text{,}n$ are 100-digit numbers. If we simply computed $a^b\text{,}$ then reduced mod $n\text{,}$ the computer’s memory would overflow: The number $a^b$ has more than ${10}^{100}$ digits, which is more digits than there are particles in the universe. However, the computation of $a^b(\text{mod}n)$ can be accomplished in fewer than 700 steps by the present method, never using a number of more than 200 digits.

Algorithmic versions of this procedure are given in Exercise 56. For more examples, see Examples 8 and 24–30 in the Computer Appendices.