密码学系列｜ 3.4 素数测试

  Bob 在学习完了第 3.2 和 3.3 两节后，现在可以使用他的 RSA公钥、私钥对与 Alice 通信。那么为了创建 RSA 密钥对，Bob 需要选择两个非常大的素数 、。对于他来说，选择两个非常大但可能是复数的 、是不行的。首先，如果 、 不是素数，那么 Bob 需要知道如何将它们分解以解密 Alice 的消息。但更糟糕的是，如果 、 的素因子很小，那么 Eve 可能能够将分解 ，从而破坏 Bob 构建的通信系统。

  因此，Bob 面临着寻找大素数的任务。更准确地说，他需要一种区分素数和复合数的方法，因为如果他知道如何做到这一点，那么他可以选择大的随机数，直到他找到一个素数为止。我们稍后将在第 3.4.1 一小节讨论随机选择的数字是素数的可能性，但就目前而言，知道他有相当大的成功率就足够了。因此，Bob 真正需要的是一种有效的方法来判断一个非常大的数是否为素数。

  比如，Bob 选择了一个随机大数 ，他想知道  是不是一个素数。首先， Bob 尝试搜索一个小的因子，但是他发现任何小于  的数都不能整除 ，于是他觉得也许  是一个素数，然后他计算 ，发现

  那么尽管上式并不能给出  的因式分解，也能够说明  并不是一个素数。为什么呢？回顾一下费马小定理：如果有素数 ，那么对于任意整数 ，都有  （除非 ）。因此，如果  是素数，那么 3.6 式右手边的值应该是 。正因为其实际上不是 ，于是 Bob 能够判断  不是一个素数。

  在继续介绍 Bob 寻求大素数的传奇之旅前，我们先陈述一下费马小定理的另一个更通用的版本，这里对  没有限制。

定理 3.16 （费马小定理，版本2） 设素数 ，那么有

证明：如果 ，那么由第一个版本的费马小定理（定理 1.24）我们有 ，同余式两边同时乘以  我们就可以得到式 3.7 了。另外，如果 ，那么式 3.7 两边同时为 。

  我们回到 Bob 的问题，Bob 又选择了一个随机数字

  同上再次检测了一些小数值后，Bob 计算了 ，发现

  那么通过式 3.9，再结合上费马小定理（定理3.16）就能够证明  是一个素数了么？答案是：NO。费马小定理讲述的并非是一个充要条件，而是单向的，是一个充分条件：如果  是一个素数，那么 。但并不能说如果满足 ，  就一定是一个素数。举一个小例子。

  然而，在某种模糊的哲学意义上，如果满足  的话，那么  大概率是一个素数。而如果  的结果不是  的话，那么我们就能知道  就是一个合数。于是我们有了如下定义。

定义 固定整数 ，我们说一个  是  （为合数）的见证，如果满足

  正如我们之前所观察到的， 的一个见证与费马小定理（定理3.16）相结合，足以毫无疑问地证明  是复合的。因此，判断  为素数的可能性的一种方法是尝试大量的数字 、、。如果其中任何一个是 的见证，那么 Bob 知道  是复合的；如果他们都不是  的见证人，那么Bob 可以怀疑，但也不确定， 是素数。

  不幸的是，像  这样的野蛮数字闯入了这个田园诗般的场景。数字  是复合的，，但  没有见证！也就是说

  没有见证的合数我们称之为 Carmichael number（R.D. Carmichael 在 1910 年发表的 paper 中列出了15个这样的数）。可以通过检测  并计算  来验证 561 是一个Carmichael number。但是练习 3.14 给出了一个更简单的方法和更多的 Carmichael number。尽管 Carmichael number 比较稀有，但是 Alford, Granville, and Pomerance 在1994 年证明了有无数个Carmichael number。所以 Bob 需要一些比费马小定理更强的工具去检测一个数值的素性。而素数的以下性质用于制定Miller–Rabin test，该 test 具有一个令人满意的性质，即每个合数都会有大量的见证。

命题 3.17 设  为一个奇素数，并写作

设  为任意一个不被  整除的数，那么其具有以下两个性质中的其中一个：

2.  中的其中一个模  与  同余

证明：由费马小定理（定理1.24）我们可知 

  我们知道上述列表中的最后一项与  相等，且模  下与  同余。并且，列表中的每一个指值都是前者的二次方，因此必定会出现一下两种情况之一：

1. 列表中的第一个值模  下与  同余

2. 列表中的某个值不满足模  下与  同余，但是平方后模  下与  同余。但是满足

   的值只有 ，所以列表中的某个值模  下与  同余。

证毕。

定义 设有奇数  并些 ，其中  为奇数。当一个整数  满足以下两个条件并且 ，那么我们称  为整数  （为合数）的Miller–Rabin见证。

  根据命题3.17，如果对于  存在Miller–Rabin见证，那么  肯定是一个合数。对于合数的 Miller–Rabin 测试流程我们用表 3.2 表示：

  现在假设 Bob 想要检测一个大数  是否为一个可能的素数，他可以随机选择几个整数  然后对整数 进行 Miller–Rabin 测试。为什么 Miller–Rabin 测试比用费马小定理测试好？因为对于 Miller–Rabin 测试来说，不存在 Carmichael-like 的数。实际上，没有给合数都会有大量的 Miller–Rabin 见证。

命题 3.18 设  为一个奇合数，那么在  中至少有 75% 的数为  的 Miller–Rabin 见证,

证明：证明并不复杂，但这里不直接给出，可以见《A Computational Introduction to Number Theory and Algebra》的 定理 10.6

  现在考虑 Bob 对大素数的识别。他拿到一个潜在素数 ，并选择是个不同的值  对  做 Miller–Rabin 测试，如果任何一个整数  是  的 Miller–Rabin 见证，那么 Bob 知道  是一个合数。但是假设所有的  都不是  的 Miller–Rabin 见证。根据命题 3.18 我们可知，如果  是一个合数，那么Bob每次进行 Miller–Rabin 测试的时候就会有至少 75% 的概率找到  的见证。由于 Bob 十次都没有找到  的见证，那么  为合数的概率最高只有 ，约等于 。并且如果觉得这还不够，那么 Bob 可以选择 100 个不同的 ，如果没有  的见证，那么  为合数的概率就低于 。

例 3.19 我们将使用整数  对 Carmichael 数  进行 Miller–Rabin 测试。首先我们分解

并且计算

  第一个数 ，既不是  也不是 ，并且列表中也没有其他值为 ，所以 2 是 Miller–Rabin 见证，因此  是一个合数。

例 3.20 我们继续第二个例子，设 ，

  我们用  对其进行 Miller–Rabin 测试。

  因此  不是  的 Miller–Rabin 见证。接下来我们用 ，不幸的是

  所以  也不是  的 Miller–Rabin 见证，也许  真的是一个素数呢？但我们继续测试，设 ，我们发现

  因此  是  的 Miller–Rabin 见证，所以  实际上是一个合数。事实上， 是一个 Carmichael 数，但并不是很好分解（by hand)。

3.4.1 The Distribution of the Set of Primes

  如果Bob随机选择一个数字，它是素数的可能性是多少？数论中著名定理之一提供了答案。为了说明这个定理，我们需要一个定义。

定义 对于任意整数 ，我们设

  比如  因为  到  中由四个素数 

定理 3.21 （The Prime Number Theorem）

证明：1896年，Hadamard 和 de la Vall´ee Poussin 分别各自证明了素数定理。不幸的是，证明远远超出了本书的范围。最直接的证明使用了复分析；参见《Introduction to Analytic Number Theory》第13章。

例 3.22 我们期望在 900000 与 1000000 之间能找到多少个素数？根据素数定理

  事实上 900000 与 1000000 之间有7224个素数。

  在密码学中我们会使用更大的素数，比如，我们可能想使用大约有300个十进制数字的素数，即是1024位，因为 

  那么有多少个素数满足 ？，根据素数定理我们有

  因此在这个区间中有大量的素数。

  直觉来看，根据素数定理，如果我们观察  到   之间的所有数字，那么它们的素数比例大约是。把这句话反过来，即：

  随机选择一个数 ，有  的概率为素数。（3.10）

  它描述了人们期望在  区间内能够找到多少素数。有关（3.10）的更精确陈述，请参见练习3.19，该陈述既有意义，又在数学上正确。

例 3.23 我们通过寻找1024位素数，即大约为  的素数，来说明（3.10）和素数定理。（3.10）表示，随机数 为素数的概率约为 。因此，Bob平均检查大约700个随机数能够找到一个素数。

  如果 Bob 足够聪明，他会做得更好。他知道他不想要一个偶数，也不想要一个可以被  整除，也不想要一个可以被  整除的数等等。因此，Bob 可能会将注意力限制在与 、、、、 互素的数上，而不是完全随机数。为此，他首先选择一个与  互素的随机数，比如说他选择 。然后他只考虑具有如下形式的数字 

  那么具有这种的形式的数字  为素数的概率为（见练习3.20）

  那么如果 Bob 随机选择一个具有 (3.11) 形式的数字 ，那么其为素数的概率约为 。因此他只需要检测 150 个随机数就有很大的机会找到一个素数。

  我们使用 Miller–Rabin 测试，选择100个随机数  去测试具有如下形式的数的素性

  我们发现对于以下的  ， 可能为素数

  这个结果比素数定理预测的大约会有 7 个素数的结论要好一些。在这里我们发现的最小的可能为素数的值为，其值为一个308十进制长度的数

202767145582614733733139403843879254621949551824058993311339593493341055229837512127224893854863968851947003448487753250093654475567042186503162873426359974273751871978241831537235413710389881550750303525056818030281312537212445925881220354174468221605146327969430834440565497127875070636801598203824198219369

注 3.24 关于素数的分布有许多悬而未决的问题，其中最重要和最著名的当然是黎曼假设。陈述黎曼假设的通常方法需要一些复分析。黎曼-泽塔函数  由级数定义

  当 s 是实数部分大于1的复数时收敛。它有一个到整个复平面的解析延拓，在 s=1 处有一个简单的极点，没有其他极点。黎曼假设说如果 ，其中  为实数，并且 ，那么有 

  乍一看，这个有点奇怪的说法似乎与素数没有什么关系。然而，不难证明  也等于乘积

  所以  也包含了关于素数集的信息。

  有许多关于素数的说法与黎曼假设是等价的。例如，回想一下素数定理（定理3.21），对于较大的  值，。黎曼假设等价于以下更准确的陈述：

  由于积分近似等于 ，这个猜想式比素数定理更强。（见练习3.21。）

3.4.2 Primality Proofs Versus Probabilistic Tests

  Miller–Rabin 测试是一种强大而实用的可以找到“可能是素数“的大数的方法，事实上，命题 3.18 指出，每个复数都有许多 Miller-Rabin 见证，因此 50 或 100 次重复 Miller-Rabin测试提供了  为素数的确凿证据。然而，陈述的证据与证明陈述正确的严格证据之间存在差异。假设 Bob 不满足于仅仅是证据。他想完全确定他选择的数字  是素数。

  原则上，没有比这更简单的了。Bob 检查  是否可被数字 、、、 中的任何一个整除，如果这些数字都不整除 ，那么 Bob 可以完全  是素数。不幸的是，如果  很大，就说年，那么 Bob 永远也检查不完。请注意，这个朴素算法的运行时间是  ，这意味着根据第2.6节中的定义，它是一个指数时间算法。

  如果我们能用Miller–Rabin 测试来有效地、决定性地证明一个数  是素数，那就太好了。更准确地说，我们想要一个证明素性的多项式时间算法。如果黎曼假设的广义版本是真的，那么下面的命题表明这是可以做到的。（我们在注3.24中讨论了黎曼假设）

命题 3.25 如果黎曼假设的广义版本为真，则每个复合数  都有一个 Miller-Rabin 见证 ，满足

证明：《Riemann’s hypothesis and tests for primality》中证明了每一个复数  都有一个见证满足 ，《Algorithmic Number Theory: Efficient Algorithms》、《Explicit bounds for primality testing and related problems.》中给出了更准确的估计 

  因此，如果广义黎曼假设是真的，那么我们可以通过使用每一个小于 的  应用Miller–Rabin 测试来证明  是素数。如果一些  证明  的见证，那么  是复数，否则，命题3.25告诉我们  是素数。不幸的是，命题3.25的证明基于广义黎曼假设是真的这样一个假设，尽管对这个问题进行了近150年的研究，但甚至没有人能够证明原始黎曼假设。

  在公钥密码学诞生之后，尤其是在1978年RSA密码系统发布之后，人们致力于发现一种不依赖于任何未经证实的假设的多项式时间素性测试算法。2002年，M.Agrawal、N.Kayal和N.Saxena发现了这样一种算法，多年的研究达到了顶峰。对其算法的后续改进给出了以下结果。

定理 3.26 （AKS 素性测试） 对于每一个 ，存在一种算法可以在不超过 步的情况下最终确定给定数字  是否为素数。

证明：原始算法发表在《 PRIMES is in P》中。可在《Primality testing with Gaussian periods》中找到进一步的分析和改进。专著《Primality Testing in Polynomial Time: From Randomized Algorithms to “PRIMES is in P”.》对包括AKS测试在内的原始性测试进行了很好的描述。

注 3.27 定理3.26中描述的结果代表了现代算法数论的胜利。由于 AKS 算法比 Miller–Rabin 测试慢得多，因此对于实际密码学的意义还不太明朗。在实践中，如果一个数通过了选择 50-100 个随机  值的 Miller-Rabin 测试，那么大多数人都更愿意接受这个数字是素数。