图灵奖11 Michael Rabin，素数测试与自动机理论

Michael Rabin 生于1931年，在德国布雷斯劳，现在是波兰弗罗茨瓦夫。他的父亲是一个犹太人学者，1935年移民到巴勒斯坦。Michael接受了良好的基础教育，就读于海法最好的高中。

迈克尔讲述了下面的故事来解释他是如何在10岁或11岁时对数学产生兴趣的。在学校的走廊上，他遇到几个年纪较大的学生，他们正试图证明一个初等几何问题。令他高兴的是，他能够解决这个问题，而且他很享受从几个已知的几何图形推导出其他结论的经验。仅凭思考就能证明几何命题的想法启发了他学习数学。

高中时，他的数学老师是以色列前总理的叔叔以利沙·内塔尼亚胡(Elisha Netanyahu)。内塔尼亚胡本身就是一位重要的数学家，后来成为海法理工学院(Technion in Haifa)的教授和理学院院长。当内塔尼亚胡还是一名高中教师时，他每周组织一次研讨会，向一些精选出来的学生讲授高等数学的主题。拉宾参加了，很快学到了比他这个年龄的学生所能学到的多得多的东西。

拉宾16岁就高中毕业了。像他的大多数同学一样，他后来应征入伍，为当时新成立的以色列的独立而战。他以阅读数学教科书来空闲时间。一个是耶路撒冷的亚伯拉罕·弗伦克尔教授写的集合论，拉宾写信给他。弗伦克尔对信内容的深度印象深刻，他会见了拉宾，后来帮助拉宾从军队中调出，进入耶路撒冷大学(University of Jerusalem)学习。他被直接录取攻读代数硕士学位，并于1953年毕业。他的论文解决了德国数学家埃米·诺特提出的一个重要的开放性问题。

在这篇论文的帮助下，他被普林斯顿大学的一个博士项目录取，在那里他师从阿朗佐·丘奇，并于1957年毕业。在拉宾完成他的博士学位后，他被IBM邀请参加一个为一群精选的年轻科学家举办的夏季研究研讨会。正是在那里，他和达纳·斯科特(Dana Scott)合作发表了著名的论文《有限自动机和他们的决策问题》，这篇论文让他们在1976年共同获得了图灵奖。

自动机理论真正开始于1943年沃尔特·皮茨和沃伦·麦卡洛克对人工神经网络的研究。其他人则继续这项受生物启发的工作。拉宾和斯科特放弃了神经网络，转而使用一种被称为有限状态机的计算模型。这些理论机器，像图灵机一样，根据输入和定义的转换规则从一个状态移动到另一个状态。有限状态机之前已经被研究过，但拉宾和斯科特考虑了不同的类型。一种是不确定的机器，它不仅有一个可能的状态转换，而是有多个。从本质上说，机器在接受一个输入符号后，就可以复制自己，然后每台机器就可以沿着一个可能的转换进行计算。正如在图灵奖的引用中提到的，非确定性机器的概念在许多问题的理论研究中被证明是非常有价值的，并将继续激励新的工作。

第二年夏天，拉宾再次被邀请参加IBM的研究研讨会。他遇到了后来的另一位图灵奖得主约翰·麦卡锡，麦卡锡向他解释了一个关于间谍和警卫的谜题。间谍们有从敌国领土进入自己领土的密码。因此，即使敌人知道了密码，间谍也能安全返回，而敌人的潜入者则不能进入。一种解决方法来自于中平方法，它是由数学家约翰·冯·诺伊曼提出的一种产生随机数的方法。每个间谍都得到一个100位的数字x，而警卫则得到另一个100位的数字，这个数字是从x2中取中间数得到的。当间谍返回时，他给警卫x。警卫计算x2，并将中间的数字与他拥有的密码进行比较。即使守卫将自己的数字传递给敌人，敌人也很难确定最初的数字是什么，即x2的100个中间数字。

拉宾开始思考一些很难求倒数的函数，在这种情况下，计算原来的x只知道x2的中间位数。他的研究成果是开创性的论文《计算函数的难易度和递归集的偏序》，这是他后来在计算复杂性特别是与密码学相关的理论研究中取得进展的起点。

拉宾回到耶路撒冷大学，先是担任高级讲师，然后是副教授，最后是教授。他保持着惊人的研究成果，同时也成为了数学研究所的主席，计算机科学系的主席，以及整个大学的校长(学术带头人)。

1975年，在雷克托大学结束了他的任期后，他去了麻省理工学院做客座教授，和加里·米勒一起研究质数测试。这涉及到确定一个非常大的数是否是质数------这个数除了自己和1以外没有除数。米勒早先在未经证实的黎曼假设的基础上开发了一个原始检验。这让拉宾感到困扰，因为如果黎曼假设最终被证明是错误的，那么基于黎曼假设的任何方法都会受到质疑。Michael之前研究过概率自动机，这是一种理论机器，使用一个随机数来决定从每个状态进行哪个转换。虽然从它总是提供一个可证明的结果的意义上说，它不是确定性的，但如果运行多次，出错的可能性就会变得非常小。拉宾利用这个概念开发了一个素数测试算法，称为米勒-拉宾测试。后来证明它是确定性的:如果进行了一定数量的测试，就保证它是有效的。

为算法添加随机性是拉宾后来许多不同问题研究的主题。他个人最喜欢的,正方形的问题,首先讨论了约瑟夫·路易斯·拉格朗日1770年,是如何表达一个整数的和四个方块:对于任何整数y不一定找到四个独特,整数a, b, c, d,

。拉格朗日表明,它总是可能的,但没人知道找到一个高效的算法,b, c和d。在一个班的学生在麻省理工学院拉宾在1977年提出了一个随机算法,他和杰夫Shallit之后出版的一部分随机算法的研究。

拉宾后来的工作涉及防止网上盗版的密码问题。最近，他一直在研究如何确保在线拍卖的隐私和保密性。在谷歌进行的广告时段拍卖中，参与者希望自己的身份和投标策略保持匿名，但希望确保拍卖结果是公平的。拉宾作为顾问，创造了一个零知识证明(zero-knowledge proof)来提供这样的保证。