邁克爾·拉賓 (科學家)

邁克爾·拉賓
Michael Oser Rabin
邁克爾·拉賓; Michael Oser Rabin
出生	1931年9月1日（92歲）; 德國魏瑪共和國布雷斯勞（今波蘭弗羅茨瓦夫）
知名於	米勒-拉賓素數檢驗; 拉賓密碼系統（英語：Rabin cryptosystem）; 不經意傳輸; 拉賓-卡普字符串搜索算法; 非確定有限狀態自動機; 隨機化算法
獎項	圖靈獎 (1976); Paris Kanellakis Award（英語：Paris Kanellakis Award） (2003); 以色列獎; 艾邁特藝術科學與文化獎（英語：EMET Prize）; 哈維獎; 丹·大衛獎; 戴克斯特拉獎（英語：Dijkstra Prize）; IEEE計算機協會查爾斯-巴貝奇獎（英語：International Parallel and Distributed Processing Symposium#IEEE Computer Society Charles Babbage Award）
	科學生涯
研究領域	計算機科學
機構	哈佛大學; 希伯來大學; 哥倫比亞大學

邁克爾·O·拉賓（希伯來語：מִיכָאֵל אֹשֶׁר רַבִּין‎，英語：Michael Oser Rabin，1931年9月1日— ）是一名以色列計算機科學家，1976年圖靈獎得主。

生平

拉賓出生於德國布雷斯勞（二戰後成為波蘭弗羅茨瓦夫），父親是一個拉比。

1953年，他獲得希伯來大學的理學碩士，1956年獲普林斯頓大學博士學位。

1959年，拉賓和達納·斯科特共同發表了「有限自動機與其判定性問題」（Finite Automata and Their Decision Problems）的論文，提出了非確定自動機的觀點。他們也因此獲得了1976年的圖靈獎，並做「計算機複雜性」（Complexity of Computations）的演講。圖靈獎的引文是：

“

因他們的合著論文「有限自動機與其判定性問題」。論文中引入了非確定自動機的概念，被證明是（計算理論科學研究中的）一個非常重要的概念。拉賓和斯科特的這篇經典論文成為了這個領域後續研究的源泉。^[1]

”

非確定自動機已經成為計算複雜度理論中的一個重要概念，特別是在描述P與NP問題的複雜度類時。

1969年，拉賓證明N successors的二階邏輯是可判定的。^[2]證明的關鍵部分暗示了奇偶遊戲（英語：Parity game）的確定性。1975年，拉賓發明了米勒-拉賓檢驗，這是一個相當快速的隨機化算法（有較小的可能性錯誤），用於判斷一個大數是否是素數。^[3]^[4] 快速素數檢驗是目前大部分公鑰密碼體系的關鍵。1979年，拉賓發明了第一個非對稱密碼系統——拉賓密碼系統（英語：Rabin cryptosystem）。它的安全性被證明和整數因式分解的複雜度相同。^[5]1981年，拉賓提出了不經意傳輸技術。^[6] 1987年，拉賓和理查德·卡普提出了一個著名的字符串搜索算法——拉賓-卡普算法。^[7]

參考

^ 英文為：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. ACM Turing Award Citation^{[永久失效連結]}
^ Rabin, MO. Decidability of second order theories and automata on infinite trees. Trans. AMS. 1969, 141: 1–35 [2009-01-06]. doi:10.2307/1995086. （原始內容存檔於2020-06-12）.
^ Rabin, MO. Probabilistic algorithms. Algorithms and Complexity, Proc. Symp. Pittsburgh. 1976.
^ Rabin, MO. Probabilistic algorithm for testing primality. Journal of Number Theory. 1980, 12 (1): 128–138. doi:10.1016/0022-314X(80)90084-0.
^ Rabin, MO. Digital signatures and public-key functions as intractable as factorization (PDF). {MIT Laboratory of Computer Science Technical Report. January 1979 [2007-03-15]. （原始內容 (PDF)存檔於2006-09-21）.
^ Rabin, Michael O., How to exchange secrets by oblivious transfer (Technical Report TR-81) (PDF), Aiken Computation Laboratory: Harvard University, 1981 [2009-01-06], （原始內容存檔 (PDF)於2021-11-23）
^ Karp, RM; Rabin, MO. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development. March 1987, 31 (2): 249–260 [2007-03-15].

外部連結

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 （頁面存檔備份，存於網際網路檔案館）

[1] 英文為：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. ACM Turing Award Citation^{[永久失效連結]}

[2] Rabin, MO. Decidability of second order theories and automata on infinite trees. Trans. AMS. 1969, 141: 1–35 [2009-01-06]. doi:10.2307/1995086. （原始內容存檔於2020-06-12）.

[3] Rabin, MO. Probabilistic algorithms. Algorithms and Complexity, Proc. Symp. Pittsburgh. 1976.

[4] Rabin, MO. Probabilistic algorithm for testing primality. Journal of Number Theory. 1980, 12 (1): 128–138. doi:10.1016/0022-314X(80)90084-0.

[5] Rabin, MO. Digital signatures and public-key functions as intractable as factorization (PDF). {MIT Laboratory of Computer Science Technical Report. January 1979 [2007-03-15]. （原始內容 (PDF)存檔於2006-09-21）.

[6] Rabin, Michael O., How to exchange secrets by oblivious transfer (Technical Report TR-81) (PDF), Aiken Computation Laboratory: Harvard University, 1981 [2009-01-06], （原始內容存檔 (PDF)於2021-11-23）

[7] Karp, RM; Rabin, MO. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development. March 1987, 31 (2): 249–260 [2007-03-15].

[1]

[2]

[3]

[4]

[5]

[6]

[7]