图灵奖得主离世：他发明的算法每天保护你的密码

你可能从未听说过迈克尔·拉宾（Michael Rabin），但每次你输入密码、完成一笔在线支付，甚至打开一个加密文件，都在使用他60多年前奠定的数学基础。

2026年4月14日，这位94岁的计算机科学家离世。他与达纳·斯科特（Dana Scott）因计算复杂性理论获得1976年图灵奖——计算机界的诺贝尔奖。但拉宾的真正遗产远比奖项更具体：他发明的算法至今仍是互联网安全的基石。

一个反直觉的事实

拉宾最知名的贡献——拉宾-卡普算法（Rabin-Karp algorithm）、拉宾密码系统（Rabin cryptosystem）、以及概率算法（probabilistic algorithm，即随机化算法）——都诞生于他对"不确定性"的拥抱。

在1960年代的计算机科学界，这几乎是异端。当时的工程师追求确定性：给定相同输入，必须产生相同输出。拉宾却证明，允许算法抛硬币做随机选择，反而能解决确定性方法无法触及的问题。

更奇怪的是，这种"随机性"最终成了安全性的来源。你的HTTPS连接、数字签名、区块链交易，都依赖拉宾开创的数学框架。

从纳粹德国到耶路撒冷的逃亡者

拉宾1931年生于德国布雷斯劳（今波兰弗罗茨瓦夫），父亲是犹太教拉比。1935年，4岁的他随家人逃往巴勒斯坦托管地——比大屠杀全面爆发早了四年。

这段经历塑造了他对"安全"的执念。他在海法最好的高中学习，老师是后来成为以色列著名数学家的以利沙·内塔尼亚胡。1948年阿以战争爆发，17岁的拉宾被征入伍，数学家亚伯拉罕·弗兰克尔亲自向军方交涉，将他提前释放进入大学。

29岁担任希伯来大学数学研究所所长，33岁成为正教授。但拉宾后来回忆："当时完全没有 appreciation（认可）计算问题的研究价值。数学家不承认这个新兴领域。"

正方：随机性是计算的本质突破

拉宾1959年在IBM兰姆庄园的夏天改变了计算机科学。他与达纳·斯科特合作的论文《有限自动机及其判定问题》引入了非确定性自动机（nondeterministic automata）——一种允许机器"猜测"正确路径的理论模型。

这直接催生了计算复杂性理论的核心分类：P与NP问题。拉宾证明，允许非确定性的机器能识别正则语言，这一框架后来成为理解"计算难度"的通用语言。

1960年在贝尔实验室，他进一步将随机性注入算法设计。概率自动机通过抛硬币决定状态转移，这种思想在1970年代演化为蒙特卡洛算法（Monte Carlo algorithm）和拉斯维加斯算法（Las Vegas algorithm）。

关键洞察：对于某些问题，随机采样能以极高概率快速找到答案，而确定性方法需要指数时间。素性测试、字符串匹配、哈希函数——这些现代计算的日常操作都受益于此。

拉宾-米勒素性测试（Rabin-Miller primality test）至今仍是生成大素数的标准方法，而你的RSA密钥就依赖这些素数。

反方：过度神化个人，忽视工程迭代

批评者指出，拉宾的理论贡献常被夸大其实际影响。非确定性自动机是优美的数学构造，但真正的编译器和硬件从未直接实现它——它更多是理论分类工具，而非工程蓝图。

概率算法的"突破"也经历了漫长工程化。拉宾1976年提出的拉宾密码系统，基于模平方根问题的计算困难性，理论上比RSA更安全。但它从未获得广泛采用：解密时可能产生四个候选明文，需要额外机制消除歧义。工程复杂性杀死了它的实用性。

更尖锐的批评是：现代密码学的真正基础设施——AES加密、椭圆曲线密码学、TLS协议——大多与拉宾无直接关联。他的贡献停留在"思想启发"层面，而非可部署的代码。

拉宾本人晚年的研究方向——零知识证明（zero-knowledge proof）、分布式系统的随机化算法——同样长期处于理论象牙塔，直到区块链兴起才找到应用场景。

我的判断：理论债务的复利效应

这场辩论的双方都有道理，但低估了理论工作的特殊时间尺度。

拉宾的贡献不是具体产品，而是"问题框架"——他定义了计算复杂性作为独立研究领域，将"效率"和"难度"转化为可证明的数学对象。这类似于图灵定义"可计算性"本身：不直接解决任何工程问题，但为所有后续工作划定疆域。

更具体地说，拉宾的随机化思想经历了两次工程化浪潮：

第一次是1970-90年代，随机化算法被纳入标准库：快速排序的随机化版本、哈希表的冲突解决、负载均衡的随机分配。这些成为每个程序员的基础工具，但 rarely 被追溯来源。

第二次是2000年代后，密码学从"保密通信"扩展为"可验证计算"。零知识证明——拉宾1970年代开始研究的领域——成为以太坊扩容方案（zk-Rollup）的核心技术。SNARK和STARK的数学基础，直接继承自拉宾与沙菲·戈德瓦瑟（Shafi Goldwasser）、西尔维奥·米卡利（Silvio Micali）等人建立的概率可验证证明框架。

一个衡量标准：拉宾的论文引用网络。他的经典工作横跨理论计算机科学、密码学、分布式系统、甚至量子计算（量子随机行走算法）。这种跨领域影响力，说明他触及的是计算的底层结构，而非特定应用。

被忽视的遗产：巴以学术走廊

拉宾的生涯还揭示了一条鲜少被讨论的技术史脉络：以色列如何成为密码学研究重镇。

1960-80年代，拉宾在希伯来大学、MIT、哈佛之间往返，培养了两代学生。他的学生包括沙菲·戈德瓦瑟（2012年图灵奖得主，零知识证明）、迈克尔·费舍尔（Michael Fischer，分布式系统共识理论）、阿维·威格德森（Avi Wigderson，2021年图灵奖得主，随机性与计算的深度理论）。

这种"学术-军事-创业"的循环在以色列尤为紧密。拉宾的学生进入以色列国防军8200部队（信号情报单位），退役后创办网络安全公司。Check Point、Wiz、Cybereason等企业的技术基因，可追溯至拉宾奠定的概率算法传统。

拉宾本人对此保持学术距离，但他的工作客观上为这一生态系统提供了数学基础设施。

最后的问题

拉宾晚年仍在活跃。2020年代，他关注量子计算对密码学的威胁，以及机器学习中的随机化优化。他最后一篇公开发表的论文讨论随机化算法在神经网络训练中的应用——94岁仍在追踪前沿。

这引出一个未被充分讨论的问题：当拉宾那一代理论家逐渐离世，谁来维护"计算复杂性"作为独立学科的地位？

当前AI研究的主流范式——规模即一切（scaling laws）、涌现能力、端到端训练——某种程度上是对复杂性理论的回避。深度学习系统难以分析、难以证明边界，与拉宾追求的"可证明效率"形成张力。

但张力也可能是双向的。近期研究表明，Transformer的注意力机制可以被重新框架为特定计算图上的随机游走——这正是拉宾1960年代研究过的数学对象。理论债务可能以意想不到的方式被偿还。

拉宾的生涯证明了一件事：最持久的贡献往往来自对基础问题的耐心拆解，而非对热点的追逐。在算法推荐决定信息 diet、生成式AI淹没原创内容的今天，这种工作方式本身是否已成为一种遗产？