Michael Rabin
Meer info
- Verbonden aan
- Hebreeuwse Universiteit van Jeruzalem, Harvard
- Bekend van
- Niet-deterministische automaten, Miller–Rabin, het Rabin-cryptosysteem, oblivious transfer
De logicus die de informatica leerde dat toeval een gereedschap is en geen hinderlijke storing.
Rabin en Dana Scott deelden in 1976 de Turing Award voor de niet-deterministische eindige automaat, beschreven in 1959. In datzelfde jaar presenteerde hij zijn probabilistische priemtest, voortbouwend op het werk van Gary Miller: Miller–Rabin schat een priemgetal nooit verkeerd in en een samengesteld getal maar zelden, en is nog steeds de manier waarop de priemgetallen achter RSA-sleutels worden gegenereerd.
Het Rabin-cryptosysteem (1979) was het eerste waarvan de veiligheid aantoonbaar gelijkwaardig was aan factorisatie. In 1981 beschreef hij oblivious transfer, een bouwsteen die Goldreich, Micali en Wigderson later gebruikten voor veilige multipartij-berekening. Met Richard Karp gaf hij in 1987 zijn naam aan het Rabin–Karp-zoekalgoritme voor strings.