迈克尔·拉宾 (科学家)
迈克尔·拉宾 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 (页面存档备份,存于互联网档案馆)
|
|