迈克尔·O·拉宾（，， ）是一名以色列计算机科学家，1976年图灵奖得主。
生平
拉宾出生于德国布雷斯劳（二战后成为波兰弗羅茨瓦夫），父亲是一个拉比，4歲遷居至巴勒斯坦託管地。
1953年，他获得希伯来大学的理学硕士，1956年获普林斯顿大学博士学位。
1959年，拉宾和达纳·斯科特共同发表了“有限自动机与其判定性问题”（）的论文，提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖，并做“计算机复杂性”（）的演讲。图灵奖的引文是：
非确定自动机已经成为计算复杂度理论中的一个重要概念，特别是在描述P与NP问题的复杂度类时。
1969年，拉宾证明N successors的二阶逻辑是可判定的。证明的关键部分暗示了的确定性。1975年，拉宾发明了米勒-拉宾检验，这是一个相当快速的随机化算法（有较小的可能性错误），用于判断一个大数是否是素数。 快速素数检验是目前大部分公钥密码体系的关键。1979年，拉宾发明了第一个非对称密码系统——。它的安全性被证明和整数因式分解的复杂度相同。1981年，拉宾提出了不经意传输技术。 1987年，拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。
参考
外部链接
- [http://www.sis.pitt.edu/~mbsclass/hall_of_fame/rabin.html Short Description in an Information Science Hall of Fame at University of Pittsburgh]
- [https://archive.today/20060206101442/http://cri.haifa.ac.il/index.html?http://cri.haifa.ac.il/events/2005/graph/oblivious.htm Oblivious transfer]
- [http://www.digitas.harvard.edu/cgi-bin/wiki/ken/RabinismCollection Quotes from some of Professor Rabin's classes]
- [http://www.columbia.edu/cu/cs4261/ Website for one of Rabin's courses]
评论 (0)