6.10 How to Test Whether a Number is a Prime? 121prime ton. In other words, they satisfy
n|an−^1 − 1for everyasuch that gcd(n, a) = 1. The smallest such number isn= 561.
While such numbers are very rare, they do show that the Fermat test is
not completely satisfactory.
The Miller–Rabin test.But in the late 1970’s, M. Rabin and G. Miller
found a very simple way to strengthen Fermat Theorem just a little bit,
and thereby overcome the difficulty caused by Carmichael numbers. We
illustrate the method on the example of 561. We use some high-school
math, namely, the identityx^2 −1=(x−1)(x+ 1), to factor the number
a^560 −1:
a^560 −1=(
a^280 − 1)(
a^280 +1)
=
(
a^140 − 1)(
a^140 +1)(
a^280 +1)
=
(
a^70 − 1)(
a^70 +1)(
a^140 +1)(
a^280 +1)
=
(
a^35 − 1)(
a^35 +1)(
a^70 +1)(
a^140 +1)(
a^280 +1)
.
Now suppose that 561 were a prime. Then by Fermat’s “Little” Theorem,
it would have to dividea^560 −1 for every 1≤a≤560. If a prime divides
a product, it divides one of the factors (exercise 6.3.3), and hence at least
one of the relations
561 |a^35 −1 561|a^35 + 1 561|a^70 + 1 561|a^140 + 1 561|a^280 +1
must hold. But already fora= 2, none of these relations hold.
The Miller–Rabin test is an elaboration of this idea. Given an odd integer
n>1 that we want to test for primality, we choose an integerafrom the
range 0≤a≤n−1 at random, and consideran−a. We factor it as
a(an−^1 −1), and then go on to factor it, using the identityx^2 −1=
(x−1)(x+ 1), as long as we can. Then we test that one of the factors must
be divisible byn.
If the test fails, we can be sure thatnis not a prime. But what happens
if it succeeds? Unfortunately, this can still happen even ifnis composite;
but the crucial point is thatthis test gives a false positive with probability
less than^12 (remember that we chose a randoma).
Reaching a wrong conclusion half of the time does not sound so good
at all; but we can repeat the experiment several times. If we repeat it 10
times (with a new randomly chosenaeach time), the probability of a false
positive is less than 2−^10 < 1 /1000 (since to conclude thatnis prime, all 10
runs must give a false positive, independently of each other). If we repeat
the experiment 100 times, the probability of a false positive drops below
2 −^100 < 10 −^30 , which is astronomically small.