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 If we first compute 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 and repeatedly square both sides to obtain the following congruences:
Since (this just means that 1234 equals 10011010010 in binary), we have
Note that we never needed to work with a number larger than
The same method works in general. If we want to compute we can do it with at most multiplications mod and we never have to work with numbers larger than This means that exponentiation can be accomplished quickly, and not much memory is needed.
This method is very useful if are 100-digit numbers. If we simply computed then reduced mod the computer’s memory would overflow: The number has more than digits, which is more digits than there are particles in the universe. However, the computation of 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.