麥可·拉賓 (科學家)

提示：此條目的主題不是麥可·拉賓 (小提琴家)。

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

麥可·拉賓 Michael Oser Rabin
出生	(1931-09-01) 1931年9月1日（93歲） 德國魏瑪共和國布雷斯勞（今波蘭弗羅茨瓦夫）
知名於	米勒-拉賓素數檢驗 拉賓密碼系統（英語：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）
科學生涯
研究領域	計算機科學
機構	哈佛大學 希伯來大學 哥倫比亞大學

生平

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

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]