第二季 · 第 35 章

如何判断一个天文数字是不是素数？

《算法的故事》第二季 · 第一篇：数学家的秘密武器——从费马的数学猜想到 Miller–Rabin 的概率革命

1970年代，一间大学的计算机实验室里。假设有人递给一名数学家一个拥有三百位数字的整数。他只提出一个问题：这是一个素数吗？这个问题听起来甚至有些幼稚。小学生就知道，素数是只能被1和自身整除的大于1的整数。2是素数。3是素数。5、7、11、13也是素数。判断15是不是素数，更是轻而易举。因为：

15=3\times5

但是，当整数拥有三百位数字时，事情发生了根本性的改变。这个数字可能有无数个潜在的约数需要排除。如果采用最直接的试除法，即使每秒能够检查十亿个候选除数，也可能需要远远超过人类文明历史的时间。然而，进入二十世纪后期，数学家发现了一种令人难以置信的可能。我们也许不需要找出一个巨大整数的任何因子，就能够判断它是不是合数。更奇妙的是，有些算法甚至不需要每次都给出绝对确定的素数结论。它们可以随机选择一些数字作为证人，让这些数字去检验一个整数。只要其中一个证人揭穿了它，算法就能断言：这个数一定是合数。如果所有证人都没有发现问题，算法则给出一个带有严格错误上界的判断。这种方法最终被称为 Miller–Rabin 素性测试。它所讲述的，不只是计算机怎样识别素数。更是一段跨越三百多年的数学故事：人类如何从寻找绝对确定的证明，走向可以精确控制错误风险的随机化算法？

第一幕：1640年，一封关于素数的信

皮埃尔·德·费马（Pierre de Fermat，约1607—1665）。他既是一位法律工作者，也是一位影响深远的数学研究者。十七世纪的法国，数学研究并不完全发生在大学里。许多重要的数学成果通过私人书信传播。学者向远方的朋友提出难题。有人尝试证明。有人给出反例。也有人提出更加大胆的猜想。在这样一个缺乏现代学术期刊体系的年代，一封信可能就是一项数学成果最初的传播方式。1640年10月18日，皮埃尔·德·费马写信给法国数学爱好者伯纳尔·弗雷尼克尔·德·贝西（Bernard Frénicle de Bessy）。信中包含一个后来被称为费马小定理的重要结论。历史研究表明，这一结论与他们此前讨论完全数、梅森数和相关数论问题的书信往来有关。费马并没有在这封信中留下现代意义上完整展开的证明；关于这些通信的时间和内容，今天可以通过保存下来的历史文献和数学史研究进行重建。^{[MacTutor History of Mathematics][ScienceDirect]}

一个看起来不起眼的规律

先考虑数字7。我们知道7是一个素数。现在选择另一个整数2。计算：

2^6=64

将64除以7：

64=9\times7+1

余数竟然是1。再试试数字3。

3^6=729

而：

729=104\times7+1

余数仍然是1。换成5：

5^6=15625

除以7，余数还是1。这是巧合吗？费马发现了一种更加普遍的数学性质。如果

p

是素数，而整数

a

不被

p

整除，那么：

\boxed{a^{p-1}\equiv1\pmod p}

这里的符号

\equiv

，表示同余。简单来说，左边的数除以

p

，所得余数等于右边的余数。例如：

2^6\equiv1\pmod7

它与下面的表达式含义相同：

2^6\bmod7=1

这条公式拥有一个重要特征：只要 $p$ 是素数，所有与它互素的底数 $a$ 都必须满足这个关系。这不是凭经验总结出来的概率规律。它是一条可以严格证明的数学定理。

为什么这个定理成立？

我们不妨用一个非常直观的方法理解它。假设

p

是素数。考虑这些非零余数：

1,2,3,\ldots,p-1

现在选一个与

p

互素的数字

a

，将每个余数都乘以

a

，再对

p

取余。我们将得到：

a,2a,3a,\ldots,(p-1)a

它们模

p

的余数，实际上只是原来那组非零余数的一次重新排列。为什么？因为如果两个不同的数字

i,j

满足：

ai\equiv aj\pmod p

那么：

a(i-j)\equiv0\pmod p

由于

p

是素数，且不整除

a

，所以只能有：

i\equiv j\pmod p

这说明，在1到

p-1

的范围内，不会出现两个不同的数字被映射到相同余数。既然一共有

p-1

个非零余数，结果自然就是一次排列。于是，将两组数字分别相乘：

a^{p-1}(p-1)!\equiv(p-1)!\pmod p

因为：

\gcd((p-1)!,p)=1

我们能够在模

p

的意义下约去这一因子。最后得到：

\boxed{a^{p-1}\equiv1\pmod p}

证明完成。这是欧拉等后来的数学家所采用的经典证明思路之一，并非宣称费马1640年的原始书信逐字使用了这套论证。

一个危险的反向推理

现在，假设有人拿来一个很大的整数

n

。我们不知道它是不是素数。但是可以尝试计算：

2^{n-1}\bmod n

如果结果不是1，那么费马小定理告诉我们：在

n

是奇数且与2互素的前提下，它不可能是素数。这就像一场考试。所有真正的素数都必须通过。只要一个数字没有通过，我们就知道它是假冒的。可是接下来，有一个看似合理、实际上却非常危险的问题：如果它通过了考试，我们能不能断言它就是素数？不能。因为一个必要条件，不一定是充分条件。所有素数必须满足费马小定理。但满足这个同余式的数字，不一定是素数。数学史中最有意思的陷阱之一，就藏在这个区别里。

第二幕：341与561——两个会说谎的数字

数字341与561成为本幕的主角。它们都不是素数，却能让某些依赖费马小定理的测试产生误判。先来看341。它看起来没有什么特别。不是偶数。末尾不是5。各位数字之和为8，也不被3整除。如果使用简单的整数测试规则，似乎很难立即发现问题。但事实上：

\boxed{341=11\times31}

它是一个合数。现在让341接受费马测试。我们选取底数2，计算：

2^{340}\bmod341

结果竟然是：

\boxed{2^{340}\equiv1\pmod{341}}

这意味着，341通过了底数为2的费马素性测试。它成功伪装成了素数。数学家把这样的数称为伪素数（Pseudoprime），更准确地说，这里是底数为2的费马伪素数。

第一个反例，还可以更换底数

那么，为什么不再尝试其他数字呢？如果选择3、5、7等不同底数，或许就能揭穿它。确实，对于许多普通的费马伪素数，改变底数可以发现其合数身份。但是，这个方法存在一个更加严重的问题。有一类特殊合数，即使面对所有与它互素的底数，仍然能够满足费马小定理中的同余关系。其中最小的一个，就是561。

一个真正狡猾的合数

\boxed{561=3\times11\times17}

这显然不是素数。但对于任何与561互素的整数

a

，都有：

\boxed{a^{560}\equiv1\pmod{561}}

换句话说：如果费马测试只检查这种同余条件，并且选取的底数都与561互素，那么不管重复多少次，它都不会揭穿561。这种特殊的合数，被称为卡迈克尔数（Carmichael Number）。

图35-1：一个合数的完美伪装

561

它并不是素数

561=3\times11\times17

真实身份

合数

有3个不同素因子

费马测试（互素底数）

全部通过

无法仅靠这项条件揭穿

a^{560}\equiv1\pmod{561},\quad \gcd(a,561)=1

谁发现了这类数字？

1899年，数学家阿尔温·科塞尔特（Alwin Korselt）提出了一项判定这类特殊合数的数学准则。根据科塞尔特准则，一个合数

n

是卡迈克尔数，当且仅当：它不含重复的素因子，而且对于它的每一个素因子

p

，都有：

p-1\mid n-1

其中竖线表示整除。到了1910年，美国数学家罗伯特·丹尼尔·卡迈克尔（Robert D. Carmichael）给出了具体实例，561是其中最小的一个。这段历史也说明，一项数学性质的理论刻画，与人们找到具体满足条件的对象，可以发生在不同年代。^{[Quanta Magazine][ResearchGate]}

为什么561能够骗过费马测试？

将561分解成：

561=3\times11\times17

同时：

561-1=560

再看每个素因子减去1：

3-1=2

11-1=10

17-1=16

这些数全部能够整除560。

图35-2：561背后的整除结构

素因子	减去1	560是否整除
3	2	560 ÷ 2 = 280
11	10	560 ÷ 10 = 56
17	16	560 ÷ 16 = 35

如果

a

与561互素，那么它也与3、11、17分别互素。应用费马小定理，可以得到：

a^{560}\equiv1\pmod3

a^{560}\equiv1\pmod{11}

a^{560}\equiv1\pmod{17}

由于3、11、17互素，根据中国剩余定理，这些同余关系组合起来，就能得到：

a^{560}\equiv1\pmod{561}

这正是561伪装的秘密。^{[Primality Tests][Quanta Magazine]}费马测试依赖的性质，对561而言竟然全部成立。这并不是计算机程序出现了错误。也不是数学定理本身不正确。而是我们错误地把一个必要条件，当成了充分条件。

一个深刻的教训

卡迈克尔数为后来的计算机算法提出了一道真正的难题。我们不能只问：“这个数字是否通过了一项素数应该通过的测试？”还必须问：“有没有合数能够通过这项测试？”对于任何试图用有限规则识别巨大整数的算法，这都是绕不过去的问题。也正是这些会伪装的合数，推动研究者寻找更强的素性测试方法。如果简单的费马同余关系不足以揭穿它们，数学家就需要从素数的内部结构中，寻找更多可以验证的性质。新的机会，出现在二十世纪七十年代。

第三幕：二十世纪，素数突然成为计算机工业的重要资源

1970年代的计算机研究环境。随着计算复杂性理论和公开密钥密码学的发展，巨大整数的素性判定逐渐成为具有现实意义的计算问题。在费马的年代，素数主要属于数学研究。它们拥有美丽的规律，也隐藏着许多令人困惑的难题。数学家研究素数究竟有多少个，研究它们如何分布，研究哪些方程的解必须涉及素数。但到了二十世纪，素数突然获得了一种新的身份。它们开始成为信息安全系统可以使用的数学资源。

一个简单却异常困难的区别

想象你拥有两个很大的素数：

p,\quad q

把它们相乘：

N=pq

对于现代计算机，执行大整数乘法并不是什么神秘的任务。但是，如果我们只把乘积

N

交给另一个人，让他重新找出

p

和

q

，事情就可能困难得多。这就是大整数分解问题。需要注意：素性测试与整数分解是两个不同的计算任务。素性测试只问：“这个整数是不是素数？”整数分解则问：“如果它是合数，究竟由哪些素因子构成？”知道某个整数是合数，并不意味着已经找到了它的任何一个非平凡因子。这一区别，在计算机科学中十分重要。

RSA：来自1970年代的密码学需求

1976年，Whitfield Diffie 与 Martin Hellman 发表了公开密钥密码学的重要研究。随后，麻省理工学院的 Ronald Rivest、Adi Shamir 和 Leonard Adleman 开始研究具体的公开密钥密码方案。他们提出的 RSA 方案，使用两个大素数构造模数：

N=pq

相关技术报告于1977年形成，论文于1978年发表于《Communications of the ACM》。^{[MIT开放学术][dblp]}

RSA 的三位研究者：Ronald Rivest、Adi Shamir、Leonard Adleman。RSA 的提出使大素数的高效生成与验证获得更加直接的工程意义。对于需要生成 RSA 密钥的系统，挑选大素数是重要步骤之一。但一台计算机怎样找到它们？一种基本策略是：生成一个足够大的候选整数。检查它是否为素数。如果不是，就换一个候选。不断重复，直到找到符合要求的素数。这里需要解决的难题，不一定是将每个候选整数彻底分解。只要能快速判断它是否满足素性要求，就可以继续。这样，素性测试的效率便直接影响密钥生成效率。而对拥有数百位十进制数字的候选整数，最原始的试除法显然不现实。

为什么试除法会变得如此昂贵？

假设候选整数有100位十进制数字。它的量级约为：

N\approx10^{100}

如果逐个尝试可能的素因子，只需要检查到：

\sqrt N\approx10^{50}

因为如果一个合数能够分解为两个大于1的整数，那么其中至少有一个不会超过它的平方根。但

10^{50}

仍然是一个无法轻易承担的规模。即使以每秒十亿次的假设速度尝试候选，检查如此庞大的范围也会十分漫长。而更大的整数，困难程度还会迅速增加。这时候，问题已经变得非常明确。我们需要一种不必尝试海量除数，就能判断巨大整数是否为素数的算法。计算复杂性理论也在这一时期逐渐形成。研究者开始严格区分不同问题所需的运算资源，研究某些问题是否存在随输入位数呈多项式增长的算法。素性测试正成为一个具有代表性的问题。而年轻的数学家 Gary Miller，即将在这条道路上迈出关键的一步。

第四幕：1975年，米勒找到了一条通往更强测试的道路

加里·米勒（Gary L. Miller），计算机科学家。其1975年会议论文与1976年期刊论文，是后来 Miller–Rabin 素性测试的重要理论来源。1975年5月，第七届 ACM 计算理论研讨会（STOC）举行。在这一会议上，Gary Miller 发表了一项关于素性测试的研究。论文题目是：Riemann's Hypothesis and Tests for Primality《黎曼假设与素性测试》。随后，扩展研究于1976年12月发表于《Journal of Computer and System Sciences》。这项工作并不直接等同于今天使用的随机化 Miller–Rabin 算法。米勒当时研究的，是在一定数学条件下，如何构造快速而确定性的素性测试。其中一项重要结果依赖扩展黎曼假设（Extended Riemann Hypothesis，ERH）。在该假设成立的条件下，他得到了能够在输入位数的多项式时间内完成素性判定的算法。^{[数字对象标识符][CMU School of Computer Science]}

一条伟大但有条件的道路

数学家经常使用这样的研究方式：先假设某个尚未证明的重大数学命题成立。再考察在这个假设之下，能够推出哪些结论。米勒的相关研究就是这样的例子。它的重要性在于展示了一种可能：素性测试也许不需要像朴素试除法那样，随着整数规模增长而变得不可承受。但如果算法正确性的理论保证依赖一个尚未证明的猜想，那么这种保证也相应带有条件。科学家希望得到更强的结论。如果不依赖扩展黎曼假设，我们是否仍然能够设计出高效的素性测试？这还需要新的思想。

在素数里，平方根有着特殊的规律

米勒所研究的判定方法，可以从一个很简单的数学事实理解。假设

p

是奇素数。如果某个整数

x

满足：

x^2\equiv1\pmod p

那么：

x^2-1\equiv0\pmod p

将左边因式分解：

(x-1)(x+1)\equiv0\pmod p

因为

p

是素数，它整除两个整数的乘积时，必定整除其中至少一个。所以：

x\equiv1\pmod p

或者：

x\equiv-1\pmod p

也就是：

\boxed{x\equiv1\ \text{或}\ p-1\pmod p}

这个结论有一个很重要的含义。在模奇素数的意义下，1只有两个不同的平方根：1和−1。但如果模数是合数，情况可能改变。例如模15：

4^2=16\equiv1\pmod{15}

然而4既不等于1，也不等于14。它是一个在模15意义下不同于正负1的平方根。

图35-3：模15中的异常平方根

查看 SVG 配图原件

35-007-ea0ae499eb79.svg · 点击查看大图

模15时，1、4、11、14的平方都与1同余。绿色表示±1，橙色表示另外两个非平凡平方根。

这就提供了一个新的测试方向。如果某个候选整数在模运算中出现了素数不允许出现的平方根结构，那么它肯定是合数。这比单纯检查费马小定理更加敏锐。但还存在一个现实问题。我们应该怎样找到这些异常的平方根？难道要把所有数字逐一平方，寻找反例？那不又回到了低效的穷举方法吗？米勒相关测试的关键思想，是将费马小定理与反复平方的结构结合起来。不用搜索所有可能的平方根。只需要沿着特定的模幂计算路径，就有机会发现合数的证据。而下一位数学家，将让这种思想获得一种新的力量。

第五幕：1980年，拉宾让随机性成为一种数学保证

迈克尔·拉宾（Michael O. Rabin），计算机科学家，1976年图灵奖共同获得者。他将相关素性测试思路转化为具有严格错误概率界限的随机化算法。1970年代后期，概率算法已成为计算机科学中的活跃研究方向。经过前几章的学习，我们已经知道：随机数不一定只能用于模拟物理世界。它还可以直接参与算法的决策过程。例如，在蒙特卡洛积分中，算法通过随机抽样估计一个原本困难的数学量。那么，随机性是否也可以用来检验素数？迈克尔·拉宾对此进行了重要研究。他的论文：Probabilistic Algorithm for Testing Primality《一种用于素性测试的概率算法》，发表于1980年2月的《Journal of Number Theory》。^{[ScienceDirect]}拉宾所取得的关键成果，是将相关测试转化为一种无需依赖扩展黎曼假设的随机化算法，并给出明确的错误概率保证。这使素性测试进入了一个新的阶段。

让数字接受随机挑选的证人审查

想象有一个候选整数

n

。我们希望知道它是不是素数。现在，从指定范围内随机挑选一个整数

a

。这个

a

被称为测试底数。算法使用它进行一组模幂计算。如果计算结果违反了素数必须满足的数学性质，那么

a

就成为一个合数证人（Witness）。只要找到一个这样的证人，算法就能肯定地说：

\boxed{n\text{ 是合数}}

但如果

a

没有发现问题，我们暂时只能说：这个整数通过了底数

a

的测试。它可能是素数。也可能是一个碰巧骗过了该底数的合数。这样的底数有时被称为强伪证底数（Strong Liar）。

最重要的保证：四分之一

对于任意固定的奇合数

n

，在 Miller–Rabin 测试所考虑的候选底数中，能够让它通过测试的底数最多只占四分之一。因此，如果按照要求独立、均匀地随机选择测试底数，那么每一轮错误接受某个合数的概率，都有严格的上界。

\boxed{P(\text{合数通过一轮测试})\le\frac14}

重复

k

次独立随机测试，合数全部侥幸通过的概率至多为：

\boxed{P(\text{合数通过全部 }k\text{ 轮})\le4^{-k}}

这个结论，是 Miller–Rabin 算法具有现实价值的关键。^{[Wolfram MathWorld][Fermat, Miller-Rabin |]}

图35-4：增加独立轮数如何降低误判上界

测试轮数	合数误通过概率上界
1轮	25%
2轮	6.25%
5轮	约 0.0977%
10轮	约 0.0000954%
20轮	约 9.09 × 10⁻¹³
40轮	约 8.27 × 10⁻²⁵

这些是对固定奇合数、在每轮独立均匀抽样的前提下得到的最坏情况概率上界，不是现实中所有候选数字的实际误判频率。

请注意，这里有一个容易误解的地方。假如一个数字通过了20轮 Miller–Rabin 测试，我们不能直接宣称：“它是素数的概率等于

1-4^{-20}

。”因为那属于另一种概率问题。要计算一个特定候选整数在通过测试之后为素数的概率，还需要考虑候选数的来源、先验分布和测试结果等信息。Miller–Rabin 提供的是：如果被测试的整数实际上是合数，那么它在独立随机底数测试中连续逃过检查的概率有多大。这是严格、可证明的算法保证。对于大素数生成，它非常有用。而且，它具有一种特殊的不对称性。如果算法发现某个合数证人，结论一定正确。如果算法全部测试通过，则只能给出带概率保证的“很可能是素数”。也就是说：发现合数是确定的；接受素数候选则可能存在一侧错误。至此，费马时代的数论规律，与现代随机化算法真正结合起来。下一步，我们要亲自拆开 Miller–Rabin 的内部结构，看看它究竟怎样让561露出破绽。

第六幕：561的审判——一个素数证人如何揭穿合数

模幂运算与连续平方，是 Miller–Rabin 测试的计算核心。算法不需要先分解待测整数，而是从同余结构中寻找合数证据。现在，把561再次带回实验室。我们已经知道：

561=3\times11\times17

它能够骗过所有与自己互素的底数所执行的费马测试。那么，Miller–Rabin 怎样揭穿它呢？答案就在一个特殊的指数分解中。

第一步：将 $n-1$ 拆成奇数与2的幂

对于任何大于2的奇数

n

，它的前一个整数

n-1

都是偶数。所以，我们一定能够把它写成：

\boxed{n-1=2^s d}

其中：

d\text{ 是奇数}

对于561：

560=2^4\times35

因此：

s=4,\qquad d=35

我们从指数35开始，依次将指数翻倍：

35\rightarrow70\rightarrow140\rightarrow280\rightarrow560

为什么要这样做？因为对于真正的奇素数

n

，费马小定理告诉我们：

a^{560}\equiv1\pmod n

而沿着指数翻倍的过程，意味着我们可以不断将前一个模运算结果平方。这样，就能够检查它是如何最终到达1的。

第二步：选择底数2

我们选：

a=2

首先计算：

x_0=2^{35}\bmod561

结果为：

\boxed{x_0=263}

它既不等于1，也不等于：

n-1=560

因此还不能通过测试。继续平方：

x_1=263^2\bmod561=166

再平方：

x_2=166^2\bmod561=67

再平方：

x_3=67^2\bmod561=1

于是，完整过程是：

图35-5：561在底数2下的模平方链

561-1=2^4\times35

2³⁵

263

平方取余

2⁷⁰

166

平方取余

2¹⁴⁰

67

平方取余

2²⁸⁰

1

67^2=4489=8\times561+1

异常点：67² 在模561下等于1，但67既不是1，也不是560。

看到问题了吗？67平方之后，结果变成了1。但是：

67\not\equiv1\pmod{561}

而且：

67\not\equiv-1\pmod{561}

如果561是真正的素数，这种情况就不可能出现。因为我们刚刚证明过：对于奇素数，模意义下1的平方根只能是1或−1。所以，561出现了不允许出现的非平凡平方根。它的伪装被揭穿了。

\boxed{561\text{ 是合数}}

而且，我们完全没有使用：

561=3\times11\times17

这条分解信息来执行测试。算法没有先找出因子，却找到了它一定是合数的数学证据。这正是 Miller–Rabin 的重要能力。

第三步：为什么真正的素数不会被误判？

我们换一个数字：

n=17

这次选择底数：

a=3

因为：

17-1=16=2^4\times1

所以：

s=4,\quad d=1

计算从：

3^1\bmod17=3

开始。然后反复平方：

3\rightarrow9\rightarrow13\rightarrow16

最后得到：

16\equiv-1\pmod{17}

这正是测试允许的结果。由于：

(-1)^2=1

所以在继续平方之后，就可以正常到达1。这个过程没有违背素数必须满足的数学性质。因此，17通过了底数3的 Miller–Rabin 测试。注意，我们只能通过这一轮测试确认它没有出现异常。虽然17的确是素数，但对于一个未知的大整数，单次通过并不足以保证它一定是素数。

第四步：测试的正式规则

对于奇数候选

n>2

，先写成：

n-1=2^s d,\qquad d\text{ 为奇数}

选择底数：

2\le a\le n-2

计算：

x=a^d\bmod n

如果：

x=1

或者：

x=n-1

那么当前底数的测试通过。否则，最多进行

s-1

次平方：

x\leftarrow x^2\bmod n

只要其中某一次得到

n-1

，这一轮就通过。如果始终没有得到允许的结果，那么

a

就是合数证人。这就是 Miller–Rabin 的核心判断过程。^{[Wolfram MathWorld][Curacao University]}这里还有一个非常实用的技术细节。对于大整数，计算：

a^d

可能产生规模极其庞大的中间值。但我们其实不需要先计算完整的

a^d

。可以使用快速模幂（Modular Exponentiation）。不断平方，并在每一步取余。例如：

a^{2k}\bmod n = ((a^k\bmod n)^2)\bmod n

这样，就能够避免直接存储那个拥有天文数字位数的完整幂。模幂运算所需的模乘次数，可以随指数的二进制位数呈线性增长。这意味着，算法能够真正用于巨大整数，而不是只在数学公式里显得优雅。

第七幕：2047的最后一次伪装

强伪素数是 Miller–Rabin 测试的重要研究对象。即使通过一轮比费马测试更严格的检查，也不意味着候选数一定为素数。到这里，你也许已经产生了一种乐观的想法。既然 Miller–Rabin 能识别561，是否意味着它终于彻底解决了所有伪素数问题？还没有。我们再看一个数字：

\boxed{2047}

它不是素数。事实上：

2047=23\times89

但是，如果使用底数2进行 Miller–Rabin 测试，事情却会变得很有意思。由于：

2047-1=2046=2\times1023

所以：

s=1,\quad d=1023

计算：

2^{1023}\bmod2047

结果恰好是：

\boxed{1}

按照算法规则，只要第一步得到1，就通过这一轮测试。因此，2047成功欺骗了底数2的 Miller–Rabin 测试。这类数字被称为强伪素数（Strong Pseudoprime）。更准确地说，2047是底数2的强伪素数。^{[home.cit.tum.de][Wolfram MathWorld]}

随机选择第二名证人

现在，我们不再选择2。改用底数3。计算：

3^{1023}\bmod2047=1565

1565既不是1，也不是2046。而此时：

s=1

已经没有更多允许的平方步骤。因此，底数3直接证明：

2047\text{ 是合数}

这就是随机化测试的真正意义。某个合数可能骗过一位证人。但并不是所有证人都容易被骗。拉宾的贡献之一，是为这种现象提供了严格的数量界限。对于固定奇合数，能够骗过测试的候选底数最多只有四分之一。因此，独立随机选择不同底数，就可以持续降低一个合数全部通过的风险。不过，不能把这理解为“每换一次底数，风险在任何情况下都会自动除以四”。严格的概率保证依赖独立、均匀的随机抽样等条件。如果总是重复同一个底数，就不能把它当成独立的新试验。这与上一章蒙特卡洛方法的统计思想形成了呼应。随机选择并不意味着盲目相信偶然性。算法之所以可靠，是因为数学家已经证明：在合适的抽样规则下，错误情况所占的比例有明确上界。随机性负责选择测试道路；数论负责保证大多数道路能够揭穿合数。

第八幕：互动实验室——让你亲自审判素数

现代数论实验不需要依靠手算巨大幂。快速模幂运算可以在避免生成完整幂值的同时，计算余数并检查强伪素数条件。现在，我们来亲自执行 Miller–Rabin 测试。这一实验不只是展示“通过”或“失败”。它还会展示算法内部的计算轨迹。你可以选择一个候选整数，给它安排不同的测试底数，观察哪个底数可以揭穿它。特别建议先选择561。用费马测试检查底数2。再看同一个底数下，Miller–Rabin 如何发现异常的平方根。然后选择2047，分别尝试底数2和3。你会发现：一位证人的通过，并不意味着整场审判已经结束。

图35-6：交互式素性测试实验室比较费马测试与 Miller–Rabin 测试对同一个数的判断，并逐步查看计算过程。

被测试的整数

测试底数 a

费马测试结果

通过

2^(560) mod 561 = 1

Miller–Rabin 结果

确定为合数

当前底数已经找到证据

指数分解

561-1=2^{4}\times35

逐步查看模平方过程已展示 1/4 步

步骤	指数	余数
起点	2^35	263

本次实验的数学解释发现非平凡平方根：67² mod 561 = 1，但 67 并非 ±1（模 561）。因此可严格断言 561 是合数。

教学验证：561 实际是合数，可被 3 整除。该信息通过独立的试除法核实，不作为 Miller–Rabin 判断的输入。

实验问题一：一个普通伪素数

选择341。使用底数2。你会看到：

2^{340}\bmod341=1

费马测试通过。但对于 Miller–Rabin：

340=2^2\times85

从：

2^{85}\bmod341=32

开始。随后：

32^2\bmod341=1

而32既不是1，也不是340。因此，Miller–Rabin 找到了合数证人。同一个底数，使用不同强度的数学测试，竟然能够得到完全不同的结论。

实验问题二：最小卡迈克尔数

选择561。底数2。费马测试仍然通过。但 Miller–Rabin 能够发现非平凡平方根67。然后换成底数50。这次你会发现，561居然能够通过这一轮 Miller–Rabin 测试。因为：

50^{35}\bmod561=560

它恰好满足允许的

-1

条件。这说明，即使面对卡迈克尔数，Miller–Rabin 也并不保证每个底数都能够揭穿它。

实验问题三：强伪素数

选择2047。底数2通过。换成底数3，则发现合数。这个实验进一步说明：测试方法越强，能够伪装的合数通常越少，但只要是概率测试，就必须认真理解剩余的误判风险。

第九幕：把数论写成程序——一个真正可以运行的 Miller–Rabin

素性测试的工程实现，需要正确处理整数边界、快速模幂、测试底数选择及多轮检验。程序实现与数学证明同样重要。现在，我们把整套算法写成 Python。为了确保示例能够处理远大于普通机器整数范围的数字，我们使用 Python 的任意精度整数。Python 还提供一个非常方便的内置函数：

pow(a, d, n)

它能够高效计算：

a^d\bmod n

无需先生成完整的

a^d

。先写出可以观察单个底数测试结果的函数。


def miller_rabin_round(n: int, a: int) -> bool:
    """
    返回 True：通过这一轮测试，不代表已经证明是素数。
    返回 False：确定是合数。
    要求 n 为大于3的奇数，且 2 <= a <= n-2。
    """
    if n <= 3 or n % 2 == 0:
        raise ValueError("n 必须是大于3的奇数")

    if not 2 <= a <= n - 2:
        raise ValueError("底数超出允许范围")

    d = n - 1
    s = 0

    while d % 2 == 0:
        d //= 2
        s += 1

    x = pow(a, d, n)

    if x == 1 or x == n - 1:
        return True

    for _ in range(s - 1):
        x = pow(x, 2, n)

        if x == n - 1:
            return True

    return False


print(miller_rabin_round(561, 2))    # False
print(miller_rabin_round(561, 50))   # True

print(miller_rabin_round(2047, 2))   # True
print(miller_rabin_round(2047, 3))   # False

print(miller_rabin_round(97, 2))     # True

请特别注意第二行结果：

miller_rabin_round(561, 50)  # True

返回 True 并不意味着561是素数。它只代表底数50没有成功证明561为合数。这也是为什么实际使用中需要重复测试。

从单轮测试到多轮随机测试

现在，我们再实现完整版本。这次使用 Python 的 secrets 模块选择随机底数，而不是使用一个固定的简单伪随机生成器。


import secrets


def is_probable_prime(n: int, rounds: int = 20) -> bool:
    """
    False：确定是合数（或小于2）。
    True：通过测试；对于一般大整数，属于概率性结论。
    """

    if rounds < 1:
        raise ValueError("测试轮数必须至少为1")

    if n < 2:
        return False

    small_primes = [
        2, 3, 5, 7, 11, 13,
        17, 19, 23, 29, 31, 37
    ]

    if n in small_primes:
        return True

    for p in small_primes:
        if n % p == 0:
            return False

    # 此时 n 是大于37的奇数
    d = n - 1
    s = 0

    while d % 2 == 0:
        d //= 2
        s += 1

    for _ in range(rounds):
        # 在 [2, n-2] 中均匀抽取底数
        a = secrets.randbelow(n - 3) + 2

        x = pow(a, d, n)

        if x == 1 or x == n - 1:
            continue

        for _ in range(s - 1):
            x = pow(x, 2, n)

            if x == n - 1:
                break
        else:
            return False

    return True


numbers = [
    17,
    97,
    341,
    561,
    2047,
    1000000007,
    1000000009
]

for n in numbers:
    result = is_probable_prime(n, 20)

    print(
        n,
        "通过测试" if result else "确定是合数"
    )

对于这份教学实现，要理解两点。第一，随机选择测试底数后，每轮的计算过程仍然是确定性的。给定同一个整数与同一个底数，模幂结果不会随机改变。第二，20轮测试的错误上界来自于数学定理与独立抽样假设，而不是因为我们实测过20次，就能凭经验认定算法足够安全。对于真实的密码密钥生成，还应遵循适用的行业标准及经过充分测试的密码学库实现，而不是直接把这段教学代码用作完整的生产级密钥生成系统。

它的计算复杂度究竟有多低？

我们设整数

n

的二进制长度为：

L=\lceil\log_2(n+1)\rceil

那么，单次模幂运算通常只需要

O(L)

次模乘量级的操作。每一轮 Miller–Rabin 测试，也只需要与输入位数成多项式关系的计算工作。若使用朴素的大整数乘法模型，一轮测试的位运算成本可以粗略写成：

O(L^3)

实际实现中，还存在更快的大整数乘法与模运算算法。与此相比，朴素试除法可能需要检查规模约为

\sqrt n

的因子范围。由于：

\sqrt n\approx2^{L/2}

这种增长随输入位数呈指数规模。而 Miller–Rabin 则利用数论结构，将测试所需计算工作控制在输入位数的多项式增长范围内。这才是它真正的效率优势。一个拥有数百位十进制数字的整数，虽然不适合通过简单试除法逐一检查潜在因子，却可以利用快速模幂执行 Miller–Rabin 测试。上一章，我们学习蒙特卡洛方法，用大量随机试验估计困难问题的统计结果。在这里，随机算法的形式发生了变化。它不是通过随机投点估计一个几何面积。而是通过随机选择证人，寻找能够证明候选整数为合数的数学反例。同样使用随机性，却服务于完全不同的目标。

第十幕：2002年，数学家终于证明素性测试可以完全不靠运气

2002年，Manindra Agrawal、Neeraj Kayal 与 Nitin Saxena 提出了 AKS 素性测试，为这一数学问题的理论发展带来新的突破。到了二十世纪末，随机化素性测试已经十分成熟。许多计算任务都可以利用 Miller–Rabin 等算法，快速筛查大型整数。但理论计算机科学家仍然在追问：能否在不依赖未证明的数学猜想、也不依赖随机抽样的情况下，设计一个对任意输入都能在多项式时间内判定素性的算法？这是一个比“现实中能否快速找到大素数”更严格的理论问题。2002年，印度理工学院坎普尔分校的三位研究者：Manindra Agrawal、Neeraj Kayal 和 Nitin Saxena，宣布取得突破。他们提出了后来被称为 AKS 的素性测试算法。2004年，论文《PRIMES is in P》发表于《Annals of Mathematics》。其关键意义，是给出了一个无条件、确定性、通用的多项式时间素性判定算法。^{[Microsoft Research][Wolfram MathWorld]}

从概率保证走向确定性证明

这并不意味着 AKS 在实际工程中总是比 Miller–Rabin 更快。相反，在许多实际大整数素性筛查任务中，经过优化的 Miller–Rabin 仍然非常有竞争力。AKS 的突出贡献是理论性的。它证明了：对于一般整数，素性判定不必依赖随机抽样，也不必假设扩展黎曼假设成立，就能够在输入位数的多项式时间内完成。研究者因此得到了一个完整的理论答案：素性判定属于复杂性类 P。但是，现实中的素性测试仍然包含多种不同需求。

任务	典型方法	输出性质
快速筛除普通合数	小素数试除	发现因子即可证明是合数
高效筛查大型候选数	Miller–Rabin	随机测试下具有严格的单侧错误概率上界
证明一般整数的素性	AKS 等确定性方法	严格判定，无随机误判
为特定大整数提供素数证明	ECPP 等素数证明方法	可验证的素性证书

有些任务只需要快速筛选候选数。有些任务必须提供数学上可以独立核验的素性证明。有些任务还需要找到所有素因子。这三种目标不能混为一谈。尤其需要强调的是：证明一个数字是合数，并不等于完成它的素因数分解。Miller–Rabin 可以在没有找到任何素因子的情况下，检测出一个整数是合数。从费马到米勒，再到拉宾与 AKS 的研究者，数学家逐渐学会为不同的计算目标，设计不同层级的证明与保证。这条发展道路，也成为现代算法理论的一个缩影。

尾声：数学中的确定性，与计算机里的概率

让我们把时间重新拨回1640年。那时，费马正在书信中讨论素数与整除问题。他发现，当一个数是素数时，某些幂运算必然满足严格的同余关系。这是一项漂亮而正确的数学发现。但三百多年后，研究人员已经知道：有些合数能够伪装得非常成功。341能够骗过底数2的费马测试。561甚至能够通过所有与自己互素的底数所执行的费马同余测试。而当数学家发展出更强的检测方法后，2047仍然能够在底数2的 Miller–Rabin 测试中蒙混过关。这些数字仿佛不断提醒研究者：一条规律，即使对所有真正的素数成立，也未必足以完整刻画素数。但这并没有让数学家放弃。相反，他们开始寻找更复杂的结构。寻找不可能出现在素数模运算中的平方根。研究哪些底数能够证明某个整数是合数。进一步证明，对于任意奇合数，能够逃过 Miller–Rabin 检查的底数只占有限比例。随后，随机性进入了算法。不是为了让程序凭运气胡乱猜测。而是因为数学家已经证明：只要正确选择随机试验，错误风险就可以被明确控制。而且，增加独立测试轮数，可以让这种风险不断下降。到2002年，AKS 又从另一个方向证明，一般素性判定还可以采用完全确定性的多项式时间算法。从十七世纪的数论书信，到二十世纪的随机化算法，再到二十一世纪的复杂性理论突破，这个问题的形式始终非常简单：“这个整数是不是素数？”但它背后的数学，已经跨越了几百年的探索。本章最值得记住的，并不是某个巨大数字的余数。而是三个彼此联系、却又截然不同的概念：数学定理告诉我们什么必然成立。算法告诉我们怎样高效检查这些性质。概率分析告诉我们，当检查不能提供绝对确定的结论时，还能给出怎样严格的可靠性保证。上一章，我们学习蒙特卡洛方法。它允许我们接受一定的统计误差，换取对复杂问题的可计算性。这一章，我们认识了另一种随机化算法。它在寻找合数证人时不允许错误，却在接受候选素数时，允许一个可以严格控制的错误风险。这不是数学放弃了严谨。恰恰相反。它说明数学家已经能够把“不确定性”本身，变成一种可以分析、设计和证明的计算资源。真正成熟的算法，不仅知道怎样得出答案，还知道自己究竟能够为这个答案提供多强的保证。

历史档案：史实与教学重构

本章的主要历史依据包括：

MacTutor 数学史：费马1640年的书信及数论研究，用于核查费马小定理的早期历史与通信背景。
Gary Miller：1976年原始研究论文，用于核查米勒素性测试的理论来源、发表时间以及扩展黎曼假设所起的作用。
Michael Rabin：1980年概率素性测试原始论文，用于核查随机化素性测试与概率保证。
斯坦福大学：素性测试数学讲义，用于核查费马伪素数、卡迈克尔数及 Miller–Rabin 的数论基础。
Agrawal、Kayal、Saxena：《PRIMES is in P》，用于核查2002年提出、2004年正式发表的 AKS 算法。

本章关于1970年代研究实验室的开场属于问题导入的文学性设想，不对应某次确有记录的具体实验。费马1640年的通信、科塞尔特与卡迈克尔的历史贡献、米勒1975—1976年的论文、拉宾1980年的研究，以及2002—2004年 AKS 的发展，都有独立历史文献依据。341、561、2047的数学性质可以直接验证；互动实验及示例程序则为现代教学设计。

第二季 · 第一篇完结

五种算法思想，一段跨越两千年的探索

第31章	欧几里得算法——从不变量中寻找确定答案
第32章	FFT——通过分治与复用减少计算
第33章	伪随机数——用确定性规则模拟随机性
第34章	蒙特卡洛——通过随机抽样估计复杂问题
第35章	Miller–Rabin——用随机证人提供严格的错误保证

下一章预告 · 第36章

《战争中的数学家：丹齐格与单纯形法》

1947年，美国。一位年轻的数学家正在面对一组庞大的资源分配问题。飞机、人员、燃料、物资、运输路线……每种资源都有严格限制，而军事与工业部门又希望实现尽可能高的效率。如果一个计划同时受到几十种甚至上百种条件限制，究竟怎样找出其中最优的方案？下一章，我们将进入第二季的第二篇——寻找世界的最优解。从 George Dantzig 的真实研究经历出发，讲述线性规划如何诞生，单纯形法怎样在复杂的约束空间中寻找最优解，以及运筹学为什么逐渐成为现代工业与管理的重要数学工具。

——《算法的故事》第二季 · 第35章完

第一幕：1640年，一封关于素数的信

一个看起来不起眼的规律

为什么这个定理成立？

一个危险的反向推理

第二幕：341与561——两个会说谎的数字

第一个反例，还可以更换底数

一个真正狡猾的合数

561

合数

全部通过

谁发现了这类数字？

为什么561能够骗过费马测试？

一个深刻的教训

第三幕：二十世纪，素数突然成为计算机工业的重要资源

一个简单却异常困难的区别

RSA：来自1970年代的密码学需求

为什么试除法会变得如此昂贵？

第四幕：1975年，米勒找到了一条通往更强测试的道路

一条伟大但有条件的道路

在素数里，平方根有着特殊的规律

第五幕：1980年，拉宾让随机性成为一种数学保证

让数字接受随机挑选的证人审查

最重要的保证：四分之一

第六幕：561的审判——一个素数证人如何揭穿合数

第一步：将 n−1n-1n−1 拆成奇数与2的幂

第二步：选择底数2

263

166

67

1

第三步：为什么真正的素数不会被误判？

第四步：测试的正式规则

第七幕：2047的最后一次伪装

随机选择第二名证人

第八幕：互动实验室——让你亲自审判素数

通过

确定为合数

实验问题一：一个普通伪素数

实验问题二：最小卡迈克尔数

实验问题三：强伪素数

第九幕：把数论写成程序——一个真正可以运行的 Miller–Rabin

从单轮测试到多轮随机测试

它的计算复杂度究竟有多低？

第十幕：2002年，数学家终于证明素性测试可以完全不靠运气

从概率保证走向确定性证明

尾声：数学中的确定性，与计算机里的概率

历史档案：史实与教学重构

五种算法思想，一段跨越两千年的探索

《战争中的数学家：丹齐格与单纯形法》

第一步：将 $n-1$ 拆成奇数与2的幂