Robert Solovay

Randomized algorithms for testing whether a number is prime were introduced by Robert Solovay and Volker Strassen and by Michael Rabin. Each of these tests is based on an efficiently computable predicate depending on n, the number being tested for primality, and an integer b in the range [2, n]. In each case, the chosen predicate has the property that, if n is prime, then the predicate must be true for all b; therefore, a value b for which the predicate is false is a witness to the compositeness of n. Solovay and Strassen (1977) proved that, if n is composite then, for their predicate, at least half the possible choices of b are witnesses to its compositeness. Rabin (1980), using a different predicate, proved that, if n is composite then a least three-quarters of the possible choices of b are witnesses (for both predicates, typically, the fraction of witnesses is even higher than the general bound). Thus, an algorithm based on evaluating one of these predicates for a sequence of independent random choices of b never declares a prime number to be composite, and the chance of incorrectly declaring a composite number to be prime decreases exponentially with the number of random choices.

The predicate used by Rabin was previously employed in a 1976 paper by Gary Miller to construct a deterministic primality testing algorithm that runs in polynomial time assuming the validity of the extended Riemann hypothesis.

The Solovay-Strassen and Miller-Rabin tests demonstrate the power of randomized algorithms and make it possible to generate large random prime numbers and thus construct candidate instances of the RSA cryptosystem. Essentially all cryptographic systems being considered today require the generation of large primes. Of the two tests, the Miller-Rabin test is the more efficient in practice. It is included in many cryptographic products and is specified in many cryptographic standards such as the ANSI X9.80 Standard.