Michael Rabin
Más información
- Institución
- Universidad Hebrea de Jerusalén, Harvard
- Conocido por
- Autómatas no deterministas, Miller–Rabin, el criptosistema de Rabin, la transferencia inconsciente
El lógico que enseñó a la informática que el azar es una herramienta y no un estorbo.
Rabin y Dana Scott compartieron el premio Turing de 1976 por el autómata finito no determinista, descrito en 1959. Ese mismo año presentó su test probabilístico de primalidad, basado en el trabajo de Gary Miller: Miller–Rabin nunca se equivoca con un primo y rara vez con un compuesto, y sigue siendo la forma en que se generan los primos de las claves RSA.
El criptosistema de Rabin (1979) fue el primero cuya seguridad era demostrablemente equivalente a factorizar. En 1981 describió la transferencia inconsciente (oblivious transfer), una pieza que Goldreich, Micali y Wigderson usaron después para la computación multipartita segura. Con Richard Karp dio nombre en 1987 a la búsqueda de cadenas Rabin–Karp.