Michael O. Rabin
ACM Fellows
USA - 2020
citation
For fundamental, pioneering contributions to the theory of computation, probabilistic algorithms, and cryptography
Press ReleaseACM Paris Kanellakis Theory and Practice Award
USA - 2003
citation
Development of efficient randomized tests of primality
Gary Miller, Michael Rabin, Robert Solovay, Volker Strassen
For the development of efficient randomized tests of primality, enabling the practical realization of public key cryptography and demonstrating the power of randomized algorithms.
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.
ACM A. M. Turing Award
USA - 1976
READ FULL CITATION AND ESSAYcitation
Along with Dana S. Scott, for their joint paper "Finite Automata and Their Decision Problem," which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field.