迈克尔·拉宾（Michael Rabin）

迈克尔·拉宾（Michael O. Rabin）是以色列裔美国计算机科学家,随机算法与自动机理论的先驱,1976年图灵奖得主。他把概率引入算法设计,深刻改变了理论计算机科学的面貌。

概述

拉宾1931年生于德国,后移居以色列,先后任教于希伯来大学与哈佛大学。1959年,他与达纳·斯科特合作发表关于非确定有限自动机的经典论文,证明非确定自动机与确定自动机在识别能力上等价,奠定了自动机理论的基础,两人也因此共享图灵奖。此后他的兴趣转向复杂度与随机化方法。

核心贡献

• 非确定有限自动机:提出并系统研究非确定性计算模型,成为形式语言理论的基石。
• 米勒-拉宾素性测试:利用随机化在多项式时间内高效判断一个大数是否为素数,是现代密码学的重要工具。
• Rabin-Karp算法:与卡普提出基于哈希的字符串匹配算法,广泛用于文本检索与查重。
• 拉宾密码系统:一种安全性可归约到大整数分解的公钥加密方案。

应用场景

拉宾的随机化思想广泛应用于密码学中的密钥生成与素数选取、大规模文本的模式匹配、分布式系统的随机化协议以及各种概率算法。米勒-拉宾测试至今仍是生成RSA密钥时寻找大素数的标准手段之一。

常见问题

问:随机算法为什么有用?答:对许多难题,引入随机选择可以在期望意义上大幅降低时间复杂度,或以极高概率给出正确答案,工程上往往比确定性算法更简单高效。

问:米勒-拉宾测试会出错吗?答:它是概率性测试,可能把合数误判为素数,但通过多轮独立测试可把错误概率压到可忽略,实践中足够可靠。