Michael Rabin
Maggiori informazioni
- Affiliazione
- Hebrew University of Jerusalem, Harvard
- Noto per
- Automi non deterministici, Miller–Rabin, il crittosistema di Rabin, oblivious transfer
Il logico che insegnò all'informatica che la casualità è uno strumento e non un fastidio.
Rabin e Dana Scott condivisero nel 1976 il Premio Turing per l'automa a stati finiti non deterministico, descritto nel 1959. Nello stesso anno presentò il suo test di primalità probabilistico, sviluppando il lavoro di Gary Miller: Miller–Rabin non scambia mai un primo per composto e solo di rado un composto per primo, ed è ancora oggi il modo in cui si generano i primi alla base delle chiavi RSA.
Il crittosistema di Rabin (1979) fu il primo la cui sicurezza risultasse dimostrabilmente equivalente alla fattorizzazione. Nel 1981 descrisse l'oblivious transfer, un mattone che Goldreich, Micali e Wigderson usarono poi per il calcolo multiparte sicuro. Con Richard Karp diede il nome, nel 1987, alla ricerca di stringhe Rabin–Karp.