迈克尔·拉宾 (科学家)

迈克尔·O·拉宾（， ）是一名以色列计算机科学家，1976年图灵奖得主。

生平 
拉宾出生于德国布雷斯劳（二战后成为波兰弗羅茨瓦夫），父亲是一个拉比。

1953年，他获得希伯来大学的理学硕士，1956年获普林斯顿大学博士学位。

1959年，拉宾和达纳·斯科特共同发表了“有限自动机与其判定性问题”（）的论文，提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖，并做“计算机复杂性”（）的演讲。图灵奖的引文是：

非确定自动机已经成为计算复杂度理论中的一个重要概念，特别是在描述P与NP问题的复杂度类时。

1969年，拉宾证明N successors的二阶逻辑是可判定的。证明的关键部分暗示了的确定性。1975年，拉宾发明了米勒-拉宾检验，这是一个相当快速的随机化算法（有较小的可能性错误），用于判断一个大数是否是素数。 快速素数检验是目前大部分公钥密码体系的关键。1979年，拉宾发明了第一个非对称密码系统——。它的安全性被证明和整数因式分解的复杂度相同。1981年，拉宾提出了不经意传输技术。 1987年，拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

参考

外部链接 
 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 

计算机科学家
圖靈獎獲得者
以色列科學家
猶太科學家
普林斯頓大學校友
耶路撒冷希伯來大學校友
耶路撒冷希伯来大学教师
以色列猶太人
德國猶太人
西里西亞人