Cryptography Reference
In-Depth Information
In this case we have considered three intervals of length 2
20
increasing the number
size by four bits each time, which is a small change. As predicted by the Prime
Number Theorem, the number of primes (the second integer in each sublist) decreases
slowly but the number of Carmichael numbers decreases much more quickly and
there are none in the third interval. The third number in each sublist is the probability
that a random integer from this interval that passes the Fermat tests for all bases is,
nevertheless, composite (i.e., a Carmichael number).
For a long time, the problem whether there are infinitely many Carmichael num-
bers remained open: if there were only finitely many then perhaps they could all
be found and then the Fermat test would become a primality test by using all the
possible bases and excluding Carmichael numbers. This test would have been very
inefficient for it would be necessary to use a non-polynomial number of bases but this
no longer matters because it was proved in 1992 by Alford, Granville and Pomerance
[5] that the set of Carmichael numbers is infinite (they actually proved that, for
x
sufficiently large, the number
C
(
x
)
of Carmichael numbers not exceeding
x
satis-
x
2
/
7
). However, as we are going to see now, the Fermat test admits a
refinement that overcomes the difficulty posed by Carmichael numbers and gives a
primality test if all—or even a fraction of—the possible bases are used.
fies
C
(
x
)>
6.2.2 The Strong Probable Prime Test
Next we present the refinement of the Fermat test we referred to above. It is based
on the following theorem:
2
s
t , with t odd. If n does not
Theorem 6.6
Let n be an odd prime and n
−
1
=
divide b then either
b
t
≡
1
(
mod n
)
or
b
2
i
t
≡−
(
)
≤
≤
−
1
mod n
for some i with
0
i
s
1
.
b
2
i
t
mod
n
b
2
s
t
mod
n
Proof
Consider the sequence
b
t
mod
n
=
b
n
−
1
mod
n
, where
i
varies from 0 to
s
. The last of these values is equal to 1
by Fermat's little theorem and each term in the sequence is equal to the square root
of the next one modulo
n
. But the only square roots of 1 modulo
n
are 1 and
,...,
,...,
1
because
n
is prime (this follows, for example, from Theorem 2.23). This means that
if we go down the above sequence from
i
−
=
=
s
to
i
0, the first term (if any)
=
−
that is
1 must be equal to
1. Thus either all of these terms are equal to 1, in
which case
b
t
≡
1
(
mod
n
)
holds, or there is an
i
such that 0
≤
i
≤
s
−
1 and
b
2
i
t
≡−
(
)
1
mod
n
.
This result is a strengthening of Fermat's little theorembecause it shows that, when
n
is prime and does not divide
b
, then not only the congruence
b
n
−
1
≡
1
(
mod
n
)
