去年看到这段的时候就想扒到网上，却一直懒得动手。

    一直读到注解的时候，还是有点震撼的。我知道费马等一些人都热衷于“纯数学”，那些被看起来毫无实用价值的“纯理论”，可这费马检查，却是全世界的服务器每秒中都要运行无数次的 RSA 算法的理论基石。就我自己而言，每天使用 SSH 的时候都要用到。而几位科学家把这这一切联系起来的过程，实在称得上是“玄妙”了。

    《计算机程序的构造和解释》 第二版中文版 P34-35

    费马小定理：如果 n 是一个素数，a 是小于 n 的任意正整数，那么 a 的 n 次方与 a 模 n 同余。(两个数称为是模 n 的同余，如果它们除以 n 的余数相同。数 a 除以 n 的余数称为 a 取模 n 的余数，或简称为 a 取模 n)。

    如果 n 不是素数，那么，一般而言，大部分的 a < n 都将不满足上面的关系。这就引出了下面这个检查素数的算法：对于给定的整数 n，随机任取一个 a < n 并计算出 an 取模 n 的余数。如果得到的结果不等于 a，那么 n 就肯定不是素数。如果它就是 a，那么 n 是素数的机会就很大。现在再另取一个随机的 a 并采用同样的方式检查。如果它满足上述等式，那么我们就能对 n 是素数有更大的信心了。通过检查越来越多的 a 值，我们就可以不断增加对有关结果的信心。这一算法称为费马检查。

    ……

    概率方法

    从特征上看，费马检查与我们前面已熟悉的算法都不一样。前面那些算法都保证计算的结果一定正确，而费马检查得到的结果则只有概率上的正确性。说得更准确些，如果数 n 不能通过费马检查，我们可以确信它一定不是素数。而 n 通过了这一检查的事实只能作为它是素数的一个很强的证据，但却不是对 n 为素数的保证。我们能说的是，对于任何数 n，如果执行这一检查的次数足够多，而且看到 n 通过了检查，那么就能使这一素数检查出错的概率减小到所需要的任意程度。

    不幸的是，这一断言并不完全正确。因为确实存在着一些能骗过费马检查的整数：某些数 n 不是素数但却具有这样的性质，对任意整数 a < n，都有 an 与 a 模 n 同余。由于这种数极其罕见，因此费马检查在实践中还是很可靠的 注1。也存在着一些费马检查的不会受骗的变形，它们也像费马方法一样，在检查整数 n 是否为素数时，选择随机的整数 a < n 并去检查某些依赖于 n 和 a 的关系。另一方面，与费马检查不同的是可以证明，对任意的数 n，相应条件对整数 a < n 中的大部分都不成立，除非 n 是素数。这样，如果 n 对某个随机选出的 a 能通过检查，n 是素数的机会就大于一半。如果 n 对两个随机选择的 a 能通过检查，n 是素数的机会就大于四分之三。通过用更多随机选择的 a 值运行这一检查，我们可以使出现错误的概率减小到所需要的任意程度。

    能够证明，存在着使这样的出错机会达到任意小的检查算法，激发了人们对这类算法的极大兴趣，已经形成了人所共知称为概率算法的领域。在这一领域中已经有了大量研究工作，概率算法也已被成功应用于许多重要领域 注2。

    注1：能够骗过费马检查的数称为 Carmichael 数，我们对它们知之甚少，只知其非常罕见，在 100 000 000 之内有 255 个 Carmichael 数，其中最小的几个是 561、1105、1729、2465、2821 和 6601。在检查很大的数是否为素数时，所用选择是随机的。撞上能欺骗费马检查的值的机会比宇宙射线导致计算机在执行“正确”算法中出错的机会还要小。对算法只考虑第一因素而不考虑第二因素恰好表现出数学与工程的不同。

    注2：概率素数检查的最惊人应用之一是在密码学的领域中。虽然完成 200 位数的因数分解现在在计算机上还是不现实的，但用费马检查却可以在几秒内判断这么大的数的素性。这一事实成为 Rivset、Shamir 和 Adleman (1977) 提出的一种构造“不可摧毁的密码”的技术基础，这一 RSA 算法已经成为提高电子通信安全性的一种使用广泛的技术。因为这项研究和其他相关研究的发展，素数研究这一曾被认为是“纯粹”数学的缩影，是仅仅因为其自身原因而被研究的课题，现在已经变成在密码学、电子资金流通和信息查询领域里有重要实际应用的问题了。