邁克爾·拉賓 (科學家)
外觀
邁克爾·拉賓 Michael Oser Rabin | |
---|---|
![]() | |
出生 | 德國魏瑪共和國布雷斯勞(今波蘭弗羅茨瓦夫) | 1931年9月1日
知名於 | 米勒-拉賓素數檢驗 拉賓密碼系統 不經意傳輸 拉賓-卡普字符串搜索算法 非確定有限狀態自動機 隨機化算法 |
獎項 | 圖靈獎 (1976) Paris Kanellakis Award (2003) 以色列獎 艾邁特藝術科學與文化獎 哈維獎 丹·大衛獎 戴克斯特拉獎 IEEE計算機協會查爾斯-巴貝奇獎 |
科學生涯 | |
研究領域 | 計算機科學 |
機構 | 哈佛大學 希伯來大學 哥倫比亞大學 |
邁克爾·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]證明的關鍵部分暗示了奇偶遊戲的確定性。1975年,拉賓發明了米勒-拉賓檢驗,這是一個相當快速的隨機化算法(有較小的可能性錯誤),用於判斷一個大數是否是素數。[3][4] 快速素數檢驗是目前大部分公鑰密碼體系的關鍵。1979年,拉賓發明了第一個非對稱密碼系統——拉賓密碼系統。它的安全性被證明和整數因式分解的複雜度相同。[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 (頁面存檔備份,存於網際網路檔案館)
|
|