118 6. Integers, Divisors, and Primes
starting from a small number. Let us show how to do a similar trick if the
exponent is a less friendly integer, say 29. Here is a way compute 2^29 :
22 =4, 23 =8, 26 =64, 27 = 128, 214 =16, 384 ,228 = 268, 435 , 456 , 229 = 536, 870 , 912.It is perhaps best to read this sequence backwards: If we have to compute an
odd power of 2, we obtain it by multiplying the previous power by 2; if we
have to compute an even power, we obtain it by squaring the appropriate
smaller power.
6.10.1Show that ifnhaskbits in base 2, then 2ncan be computed using fewer
than 2kmultiplications.
How to avoid LARGE numbers.We have shown how to overcome the
first difficulty; but the computations above reveal the second: the numbers
grow too large! Let’s say thatnhas 100 digits; then not only is 2n−^1
astronomical, the number of its digits is astronomical! We could never write
it down, let alone check whether it is divisible byn.
The way out is to divide bynas soon as we get any number that is
larger thann, and just work with the remainder of the division (or we
could say we work in modular arithmetic with modulusn; we won’t have
to do divisions, sondoes not have to be a prime). For example, if we want
to check whether 25| 224 −1, then we have to compute 2^24 .Asabove,we
start with computing 2^3 = 8, then square it to get 2^6 = 64. We immediately
replace it by the remainder of the division 64÷25, which is 14. Then we
compute 2^12 by squaring 2^6 , but instead we square 14 to get 196, which we
replace by the remainder of the division 196÷25, which is 21. Finally, we
obtain 2^24 by squaring 2^12 , but instead we square 21 to get 441, and then
divide this by 25 to get the remainder 16. Since 16−1 = 15 is not divisible
by 25, it follows that 25 is not a prime.
This does not sound like an impressive conclusion, considering the trivi-
ality of the result, but this was only an illustration. Ifnhaskbits in base
2, then as we have seen, it takes only 2kmultiplications to compute 2n,
and all we have to do is one division (with remainder) in each step to keep
the numbers small. We never have to deal with numbers larger thann^2.
Ifnhas 100 digits, thenn^2 has 199 or 200; not much fun to multiply by
hand, but quite easily manageable by computers.
Pseudoprimes.But here comes the third shortcoming of the primality
test based on Fermat’s Theorem. Suppose that we carry out the test for a
numbern. If it fails (that is,nis not a divisor of 2n−^1 −1), then of course
we know thatnis not a prime. But suppose we find thatn| 2 n−^1 −1. Can
we conclude thatnis a prime? Fermat’s Theorem certainly does not justify
this conclusion. Are there composite numbersnfor whichn| 2 n−^1 −1?