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.
Search WWH ::




Custom Search