Cryptography Reference
In-Depth Information
for all
a
. These numbers are called
Carmichael numbers
.
21
Because it is not able
to correctly handle Carmichael numbers, the Fermat test is not widely deployed in
practice. Instead, either the Solovay-Strassen test or the Miller-Rabin test is used.
Solovay-Strassen Test
The Solovay-Strassen test is a probabilistic compositeness testing algorithm that
was developed by Robert Solovay and Volker Strassen in 1976. It can prove the
compositeness of a large number
n
with certainty, but it can prove the primality of
n
only with a certain probability.
The Solovay-Strassen test makes use of some facts related to quadratic resid-
uosity that we introduce in Section 3.3.7. More specifically, the test employs and
takes advantage of the fact that if
n
is prime, then the Legendre symbol
a
n
and
a
n
−
1
(mod
n
)
2
must be equal for every 1
1 (according to Euler's criterion stated in
Theorem 3.9 on page 93). Consequently, if one finds an
a
for which the two values
are different, then
n
must be composite (and
a
is a witness for the compositeness of
n
, respectively). Let
n
be a large odd number for which we want to decide whether
it is prime or composite. We execute the Solovay-Strassen test multiple times. In
each execution, we randomly choose an integer
a
between 1 and
n
≤
a
≤
n
−
−
1 and compute
n
) and
a
n−
1
/
2
(mod
n
). If the two values are not the
same, then
n
is composite and
a
is a witness for the compositeness of
n
. In this case,
the algorithm can abort. Otherwise (i.e., if the two computed values are the same),
the algorithm must continue with the next value of
a
. If we execute the test
k
times
and two computed values are the same for all
k
values of
a
, then we can say that
n
is prime with probability at least 1
both the Legendre symbol (
a
|
−
2
−k
.
Miller-Rabin Test
The Miller-Rabin test is another probabilistic compositeness testing algorithm that
was developed by Gary Miller and Michael O. Rabin in the late 1970s. Similar
21
It can be shown that a Carmichael number must be odd, square free, and divisible by at least 3 prime
numbers. For example, the smallest Carmichael number is 561 = 3
·
11
·
17.