Michael O. Rabin

From Wikipedia, the free encyclopedia

Michael Oser Rabin
Born	1931 Breslau, Poland
Fields	Computer Science
Institutions	Harvard University Hebrew University Columbia University
Known for	Miller-Rabin primality test Rabin cryptosystem Oblivious transfer Rabin-Karp string search algorithm Nondeterministic finite automata
Notable awards	Turing Award

For the violinist, see Michael Rabin (violinist).

Michael Oser Rabin (Hebrew: מִיכָאֵל אֹשֶׁר רַבִּין‎, born 1931 in Breslau, Germany, today in Poland) is an Israeli computer scientist and a recipient of the Turing Award.

Contents 1 Biography 2 See also 3 References 4 External links

[edit] Biography

Rabin was born as the son of a rabbi in what was then known as Breslau (it became Wrocław, and part of Poland, after the Second World War). He received an M.Sc. from Hebrew University of Jerusalem in 1953 and a Ph.D. from Princeton University in 1956.

The citation for the Turing Award, awarded in 1976 jointly to Rabin and Dana Scott for a paper written in 1959,^[1] states that the award was granted:

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.^[2]

Nondeterministic machines have become a key concept in computational complexity theory, particularly with the description of complexity classes P and NP.

In 1969, Rabin proved that the second-order theory of n successors is decidable^[3]. A key component of the proof implicitly showed determinacy of parity games, which lie in the third level of the Borel hierarchy.

In 1975, Rabin also invented the Miller-Rabin primality test, a randomized algorithm that can determine very quickly (but with a tiny probability of error) whether a number is prime.^[4][5] Fast primality testing is key in the successful implementation of most public-key cryptography.

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization.^[6]

In 1981, Rabin invented the technique of oblivious transfer,^[7] allowing a sender to transmit a message to a receiver where the receiver has some probability between 0 and 1 of learning the message, with the sender being unaware whether the receiver was able to do so.

In 1987, Rabin, together with Richard Karp, created one of the most well-known efficient string search algorithms, the Rabin-Karp string search algorithm, known for its rolling hash.^[8]

Rabin's more recent research has concentrated on computer security. He is currently the Thomas J. Watson Sr. Professor of Computer Science at Harvard University and Professor of Computer Science at Hebrew University. For the spring 2007 semester, he is a visiting professor at Columbia University teaching Introduction to Cryptography.

He was also the PhD advisor of Saharon Shelah, one of the preeminent active researchers in mathematical logic.

[edit] See also

• Oblivious transfer
• Rabin automaton
• Rabin fingerprint

[edit] References

1. ^ Rabin, MO; Scott, D (April 1959). "Finite Automata and Their Decision Problems". IBM Journal of Research and Development 3 (2): 114-125. 
2. ^ ACM Turing Award Citation
3. ^ Rabin, MO (1969). "Decidability of second order theories and automata on infinite trees". Trans. AMS 141: 1-35. 
4. ^ Rabin, MO (1976). "Probabilistic algorithms". Algorithms and Complexity, Proc. Symp. 
5. ^ Rabin, MO (1980). "Probabilistic algorithm for testing primality". Journal of Number Theory 12 (1): 128-138. 
6. ^ Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report. 
7. ^ Rabin, Michael O. (1981), How to exchange secrets by oblivious transfer (Technical Report TR-81), Aiken Computation Laboratory: Harvard University, <http://eprint.iacr.org/2005/187.pdf> 
8. ^ Karp, RM; Rabin, MO (March 1987). "Efficient randomized pattern-matching algorithms". IBM Journal of Research and Development 31 (2): 249-260. 

[edit] External links

• Short Description in an Information Science Hall of Fame at University of Pittsburgh
• Oblivious transfer
• Quotes from some of Professor Rabin's classes
• Website for one of Rabin's courses

v • d • e A. M. Turing Award laureates Perlis (1966) · Wilkes (1967) · Hamming (1968) · Minsky (1969) · Wilkinson (1970) · McCarthy (1971) · Dijkstra (1972) · Bachman (1973) · Knuth (1974) · Newell / Simon (1975) · Rabin / Scott (1976) · Backus (1977) · Floyd (1978) · Iverson (1979) · Hoare (1980) · Codd (1981) · Cook (1982) · Thompson / Ritchie (1983) · Wirth (1984) · Karp (1985) · Hopcroft / Tarjan (1986) · Cocke (1987) · Sutherland (1988) · Kahan (1989) · Corbató (1990) · Milner (1991) · Lampson (1992) · Hartmanis / Stearns (1993) · Feigenbaum / Reddy (1994) · Blum (1995) · Pnueli (1996) · Engelbart (1997) · Gray (1998) · Brooks (1999) · Yao (2000) · Dahl / Nygaard (2001) · Rivest / Shamir / Adleman (2002) · Kay (2003) · Cerf / Kahn (2004) · Naur (2005) · Allen (2006) · Clarke / Emerson / Sifakis (2007)

Persondata
NAME	Rabin, Michael Oser
ALTERNATIVE NAMES
SHORT DESCRIPTION	Polish computer scientist
DATE OF BIRTH	1931
PLACE OF BIRTH	Breslau, Poland
DATE OF DEATH
PLACE OF DEATH