Michael Rabin
More info
- Affiliation
- Hebrew University of Jerusalem, Harvard
- Known for
- Nondeterministic automata, Miller–Rabin, the Rabin cryptosystem, oblivious transfer
The logician who taught computer science that randomness is a tool rather than a nuisance.
Rabin and Dana Scott shared the 1976 Turing Award for the nondeterministic finite automaton, described in 1959. That same year he presented his probabilistic primality test, building on Gary Miller's work: Miller–Rabin never misjudges a prime and only rarely a composite, and it is still how the primes behind RSA keys get generated.
The Rabin cryptosystem (1979) was the first whose security was provably equivalent to factoring. In 1981 he described oblivious transfer, a building block that Goldreich, Micali and Wigderson later used for secure multiparty computation. With Richard Karp he lent his name to the Rabin–Karp string search in 1987.