量子素性证明

“判断一个数大概是素数”和“给出任何人都能核验的素性证明”是两件不同的事。Miller—Rabin 很快，但通过若干轮只说明合数概率很低；AKS 可以确定性判断，却不一定是实践中最省资源的证书系统。本词条从 Lucas 定理出发，推导量子阶查找如何直接产生素性证据，并讨论它与 Shor 分解、经典证书之间的取舍。

预备知识：量子傅里叶变换、相位估计与 Shor 算法。本词条不再重复推导阶查找电路本身，而是把它当作一个可以调用的黑盒：输入单位 $a$ 与模数 $N$，输出 ${\mathrm{ord}}_N(a)$。我们要回答的问题是：为什么知道一个元素的乘法阶，就能证明 $N$ 是素数？量子计算机在这里到底省掉了哪一步？

1. 问题的来龙去脉：素性判定与素性证明

给一个大整数 $N$（比如密码学中常见的几百位整数），我们想回答“$N$ 是素数吗”。这个问题的历史可以分成两条线。

第一条线是概率性判定。Fermat 小定理说，若 $N$ 是素数，则对所有与 $N$ 互素的 $a$ 都有 $a^{N-1}\equiv 1(\mathrm{mod}N)$。反过来随机挑一个 $a$ 检验这个同余式，就得到一个快速的素性“测试”：通不过一定是合数，通过了则“大概是素数”。但存在 Carmichael 数——一类合数，能让所有与它互素的 $a$ 都通过 Fermat 检验——所以单靠 Fermat 条件永远不能把合数和素数干净地分开。

最小也最著名的一个 Carmichael 数是 $561=3\times 11\times 17$。为什么它能骗过所有底数？任取 $\gcd (a,561)=1$，则 $a$ 模每个素因子都可逆，由 Lagrange 定理，它模 $3$、模 $11$、模 $17$ 的阶分别整除 $2$、$10$、$16$（即各自的群阶 $\phi (3),\phi (11),\phi (17)$）。而 $2$、$10$、$16$ 全都整除 $560$，所以

$$a^{560}\equiv 1(\mathrm{mod}3),a^{560}\equiv 1(\mathrm{mod}11),a^{560}\equiv 1(\mathrm{mod}17),$$

三个同余式模数两两互素，由中国剩余定理合并得 $a^{560}\equiv 1(\mathrm{mod}561)$。也就是说，只要底数不直接暴露因子（那种情况 $\gcd$ 检查会先抓住它），Fermat 检验对 $561$ 必然放行——这正是“Carmichael 数让所有单位都通过 Fermat 检验”的含义。Miller—Rabin 测试把条件加强为检查 $a^{(N-1)/2^k}$ 这一串幂中是否出现 $1$ 的非平凡平方根，可以证明每个合数都有至少 $3/4$ 的随机底数会“揭穿”它，重复几十轮后误判概率指数级小。这在实践中完全够用，但逻辑上它只给出“这个数是合数的概率极低”，而不是一份可以逐项核验的证明。

第二条线是确定性判定与证书。Pratt 在 1975 年指出：每个素数都有一份长度多项式有界、可以多项式时间核验的证书 (certificate)——换句话说，素性不仅好猜，而且“猜对之后可以说服别人”。2002 年 Agrawal—Kayal—Saxena (AKS) 给出第一个无条件的确定性多项式时间素性判定算法，把“素性在 P 中”变成定理；此后 Cheng、Bernstein、Morain 等人围绕 AKS 变体与椭圆曲线素性证明 (ECPP) 不断改进复杂度（见文末 Zoo 393—395 对应的工作）。这些结果表明：经典计算机原则上不需要量子帮助就能判定素性。

那么量子算法还有什么可做的？关键在于资源模型与证书形式。经典 Lucas—Pratt 证书要求先分解 $N-1$；分解一般整数正是经典计算的困难所在，而恰是量子计算机擅长的事。1995 年 Chau 与 Lo 提出用 Shor 算法分解 $N-1$、再走经典 Lucas 证书的路线（Zoo 397）；2017 年 Donis-Vela 与 Garcia-Escartin 进一步观察到：证明素性根本不需要完整分解 $N-1$，只需要一个阶为 $N-1$ 的元素，而“求一个元素的阶”可以绕开分解直接由量子阶查找完成（Zoo 396）。本词条的主线就是把这个观察讲透。

2. 数论准备：单位群、乘法阶与 Lucas 定理

设 $N>2$ 为奇数。模 $N$ 的单位群 (unit group) 定义为

$${\mathbb{Z}}_N^{\ast }=\{a\in \{1,\dots ,N-1\}:\gcd (a,N)=1\},$$

即所有与 $N$ 互素的剩余类，运算是模 $N$ 乘法。它确实是群：互素的两个数相乘仍与 $N$ 互素（封闭性）；每个元素有逆元，因为 $\gcd (a,N)=1$ 时 Bézout 等式给出 $xa+yN=1$，即 $xa\equiv 1(\mathrm{mod}N)$。看个具体例子：求 $3$ 模 $7$ 的逆元。辗转相除一步得 $7=2\cdot 3+1$，回代即 $1=7-2\cdot 3$，所以 $3^{-1}\equiv -2\equiv 5(\mathrm{mod}7)$；验算 $3\cdot 5=15\equiv 1(\mathrm{mod}7)$，正确。群的大小是 Euler 函数

$$\phi (N)=|{\mathbb{Z}}_N^{\ast }|=\#\{1\le k\le N-1:\gcd (k,N)=1\}.$$

元素 $a\in {\mathbb{Z}}_N^{\ast }$ 的乘法阶 (multiplicative order) 定义为

$${\mathrm{ord}}_N(a)=\min \{r>0:a^r\equiv 1(\mathrm{mod}N)\},$$

即让 $a$ 的幂第一次回到 $1$ 所需的最小指数。这个最小值一定存在：群有限，序列 $a,a^2,a^3,\dots$ 必然出现重复，而一旦 $a^i=a^j$（$i<j$），两边乘以 $a^{-i}$ 得 $a^{j-i}=1$。

阶的最重要性质来自 Lagrange 定理：有限群中任意元素的阶整除群的阶。对 ${\mathbb{Z}}_N^{\ast }$ 这就是

$${\mathrm{ord}}_N(a)\mid \phi (N).$$

若 $N$ 为素数，则 $1,\dots ,N-1$ 全部与 $N$ 互素，$\phi (N)=N-1$，于是 ${\mathrm{ord}}_N(a)\mid N-1$；特别地 $a^{N-1}\equiv 1(\mathrm{mod}N)$，这正是 Fermat 小定理。

反方向一般不成立：$a^{N-1}\equiv 1(\mathrm{mod}N)$ 不能反推 $N$ 是素数——Carmichael 数就是反例，它们是合数，却让所有单位都通过 Fermat 检验。问题出在 Fermat 条件只限制了“$N-1$ 是阶的倍数”，而没有限制阶本身有多大。Lucas 的关键观察是把条件加强到阶恰好等于 $N-1$：

Lucas 定理。若存在 $a\in {\mathbb{Z}}_N^{\ast }$ 使 ${\mathrm{ord}}_N(a)=N-1$，则 $N$ 必为素数。

这个定理的证明很短，我们把每一步都写出来：

• 第一步，由 Lagrange 定理，${\mathrm{ord}}_N(a)\mid \phi (N)$。假设 ${\mathrm{ord}}_N(a)=N-1$，则 $\phi (N)$ 是 $N-1$ 的正整数倍，特别地 $N-1\le \phi (N).$
• 第二步，$\phi (N)$ 数的是 $\{1,\dots ,N-1\}$ 中与 $N$ 互素的元素，这个集合总共只有 $N-1$ 个数，所以恒有 $\phi (N)\le N-1.$
• 第三步，两式夹出 $\phi (N)=N-1$，即 $1,\dots ,N-1$ 中的每一个数都与 $N$ 互素。
• 第四步，若 $N$ 是合数，它必有一个因子 $d$ 满足 $1<d\le \sqrt{N}<N$；这个 $d$ 落在 $\{1,\dots ,N-1\}$ 中，但 $\gcd (d,N)=d>1$，与第三步矛盾。所以 $N$ 是素数。Q.E.D.

值得强调的是这个条件不是空的：若 $N$ 真的是素数，这样的 $a$ 一定存在。原因是 $N$ 为素数时 ${\mathbb{Z}}_N^{\ast }$ 是阶 $N-1$ 的循环群 (cyclic group)，即存在生成元 $g$ 使 ${\mathbb{Z}}_N^{\ast }=\{g,g^2,\dots ,g^{N-1}=1\}$，而生成元的阶正是 $N-1$。我们在第 5 节证明循环性。于是 Lucas 定理给出的是一个充要的认证机制：素数一定有阶 $N-1$ 的元素，有阶 $N-1$ 的元素一定是素数。剩下的全部问题只是：怎么找到这样一个元素，又怎么向别人证明它的阶确实是 $N-1$。

3. 经典 Lucas 证书：为什么绕不开分解 $N-1$

直接验证 ${\mathrm{ord}}_N(a)=N-1$ 似乎要检查 $a^1,a^2,\dots ,a^{N-2}$ 全都不是 $1$——这是指数次工作。Lucas 证书的核心技巧是：只要知道 $N-1$ 的素因子分解，检查就塌缩成对每个素因子的一次模幂。

设已知

$$N-1=\prod _i{p}_i^{e_i},$$

其中 $p_i$ 是互不相同的素数、$e_i\ge 1$。验证以下两组条件：

$$a^{N-1}\equiv 1(\mathrm{mod}N),a^{(N-1)/p_i}\not\equiv 1(\mathrm{mod}N)\text{对每个 }i.$$

为什么这就够了？记 $r={\mathrm{ord}}_N(a)$，逐步推理：

• 由第一个条件，$r\mid N-1$（阶的基本性质：$a^m=1⟺\mathrm{ord}(a)\mid m$；证明：写 $m=qr+s$、$0\le s<r$，则 $a^s=a^m(a^r{)}^{-q}=1$，由 $r$ 的最小性得 $s=0$）。
• 把 $r$ 写成素因子分解 $r={\prod }_i{p}_i^{f_i}$，其中 $0\le f_i\le e_i$（因为 $r$ 整除 $N-1$，它的素因子不会跑出 $N-1$ 的清单，指数也不会更大）。
• 假如某个 $f_i<e_i$，那么 $r$ 整除 $(N-1)/p_i$（两边做素因子分解逐项比较指数即见），于是由上面同一条基本性质，$a^{(N-1)/p_i}\equiv 1(\mathrm{mod}N)$——与第二个条件矛盾。
• 所以对所有 $i$ 都有 $f_i=e_i$，即 $r=N-1$。Q.E.D.

核验的代价：每个条件是一次模幂，指数约 $n=\lceil {\log }_{2}N\rceil$ 位，用快速幂是 $O(n)$ 次模乘；不同素因子的个数 $i$ 最多 $O(\log N)=O(n)$ 个。所以给定 $N-1$ 的分解后，整个核验是多项式时间的。困难没有消失，只是从“求 $N$ 的因子”转移成了“分解 $N-1$”——对经典计算机来说，这一般仍是困难问题。

Pratt 证书把这个观察递归化：证书里除了 $a$ 和 $N-1$ 的分解，还递归附上每个 $p_i$ 自己的素性证书。递归在 $p_i=2$ 处终止，整棵证书树的规模可以证明是多项式有界的，核验完全经典、完全确定性。这就是“素性属于 NP”的具体含义。

用 $N=7$ 走一遍这棵递归树，它的结构就一目了然。证书内容是：

• 顶层：$N=7$，见证元 $a=3$，分解 $N-1=6=2\cdot 3$；
• 子证书 1：$p_1=2$，$2$ 是素数（递归基例，直接承认）；
• 子证书 2：$p_2=3$，见证元 $a^{\prime }=2$，分解 $3-1=2$（再次落到基例）。

核验者做的事：顶层检查 $3^6\equiv 1(\mathrm{mod}7)$、$3^{6/2}=3^3\equiv 6\not\equiv 1$、$3^{6/3}=3^2\equiv 2\not\equiv 1$（具体数值在第 9 节算出）；子证书 2 检查 $2^2\equiv 1(\mathrm{mod}3)$、$2^{2/2}=2\not\equiv 1(\mathrm{mod}3)$，即 ${\mathrm{ord}}_3(2)=2=3-1$。整棵树一共三次模幂，全是几位的算术——但前提永远是有人已经把 $6=2\cdot 3$ 分解好了。

Chau—Lo 方法（Zoo 397，1995 年）的想法到此已经呼之欲出：分解 $N-1$ 是经典困难的，但量子计算机有 Shor 算法。那就用 Shor 算法分解 $N-1$，再构造上述 Lucas—Pratt 证书。优点非常突出：最终输出的证书（$a$、$N-1$ 的分解、递归子证书）可以由纯经典验证者快速核验，量子计算机只负责“出题”，不负责“监考”。代价则是我们执行了一次完整的整数分解——而判定 Lucas 条件其实只需要知道一个元素的阶，分解给出的是多得多的信息。有没有可能只取所需、跳过分解？这正是下一节的方法。

4. 直接阶查找算法

Donis-Vela 与 Garcia-Escartin（Zoo 396，2017 年）的算法把量子子程序从“分解 $N-1$”换成“求 ${\mathrm{ord}}_N(a)$”。令 $n=\lceil {\log }_{2}N\rceil$ 为 $N$ 的位长。算法的单次迭代如下：

1. 均匀随机选择 $1<a<N$，用辗转相除法计算 $g=\gcd (a,N)$。若 $g>1$，直接输出非平凡因子 $g$：这确定 $N$ 为合数，而且 $g$ 本身就是一份可以经典核验的证据（验算一次乘法即可）。
2. 经典计算 $z=a^{(N-1)/2}\mathrm{mod}N$（$N$ 为奇数，$(N-1)/2$ 是整数；用快速幂做，$O(n)$ 次模乘）。若 $z\notin \{1,-1\}$，则 $a$ 是合数见证，输出“合数”。
3. 若 $z=1$，则 ${\mathrm{ord}}_N(a)\mid (N-1)/2$，于是 ${\mathrm{ord}}_N(a)\le (N-1)/2<N-1$，这个 $a$ 不可能是 Lucas 定理要的元素，丢弃，换一个新的 $a$。
4. 若 $z=-1$，调用 Shor 的量子阶查找，得到 $r={\mathrm{ord}}_N(a)$。
5. 若 $r=N-1$，由 Lucas 定理确定 $N$ 为素数，输出证书 $(N,a)$；否则换一个 $a$。

下面逐步说明每个分支为什么是对的。

第 2 步的两个子情形。 说“$z\notin \{1,-1\}$ 说明 $N$ 是合数”，严格来说有两条路径，都值得看清：

• 若 $z^2=a^{N-1}\not\equiv 1(\mathrm{mod}N)$，则 Fermat 小定理的逆否命题直接给出 $N$ 是合数，$a$ 是 Fermat 见证；
• 若 $z^2=a^{N-1}\equiv 1(\mathrm{mod}N)$ 但 $z\notin \{1,-1\}$，那么 $z$ 是 $1$ 的非平凡平方根：$z^2\equiv 1$ 即 $N\mid (z-1)(z+1)$，而 $z\not\equiv \pm 1$ 意味着 $N$ 既不整除 $z-1$ 也不整除 $z+1$，所以 $N$ 必有因子分在两边，$\gcd (z-1,N)$ 给出非平凡因子。模素数时 $x^2\equiv 1$ 只有 $x\equiv \pm 1$ 两个解（域上二次多项式至多两个根），所以非平凡平方根的存在本身证明 $N$ 是合数。这正是 Miller—Rabin 测试与 Shor 算法共同使用的经典技巧。

两种情形结论一致：第 2 步不会冤枉任何素数。

第 3 步为什么安全。 $z=a^{(N-1)/2}\equiv 1$ 意味着阶整除 $(N-1)/2$，所以阶至多是 $(N-1)/2$，这样的 $a$ 对 Lucas 定理无用。反过来，任何阶为 $N-1$ 的元素 $a$ 必然落在 $z=-1$ 分支：因为 $a^{(N-1)/2}$ 是 $1$ 的平方根（它的平方是 $a^{N-1}=1$），而阶为 $N-1$ 说明 $a^{(N-1)/2}\ne 1$，所以只能等于 $-1$（这里用到 $N$ 为素数时 ${\mathbb{Z}}_N^{\ast }$ 中 $1$ 的平方根只有 $\pm 1$；若 $N$ 是合数，这个 $a$ 反正也不是我们要的）。换句话说，预筛选永远不会误删真正的生成元。

第 4 步为什么值得调用量子计算机。 $z=-1$ 同时告诉我们两件事：(i) $a^{N-1}=z^2=1$，所以 ${\mathrm{ord}}_N(a)\mid N-1$；(ii) ${\mathrm{ord}}_N(a)\nmid (N-1)/2$。把 $N-1$ 的因子 $2$ 的幂次记作 ${\nu }_2(N-1)$（即 $N-1=2^{{\nu }_2}\cdot \text{奇数}$），则 (i) 说 ${\nu }_2(r)\le {\nu }_2(N-1)$，(ii) 说 ${\nu }_2(r)>{\nu }_2(N-1)-1$，合起来

$${\nu }_2(r)={\nu }_2(N-1):$$

$r$ 已经“凑齐”了 $N-1$ 的全部因子 $2$，差的只可能是奇数部分。所以这个分支里的 $a$ 是阶为 $N-1$ 的“候选者”，值得花一次量子阶查找去确认。预筛选不是正确性所必需（直接对第 1 步幸存的 $a$ 做阶查找也行），但它避免对明显无用的底数调用昂贵的量子电路，而且让阶查找的结果有明确的比较目标：只收 $r=N-1$。

第 5 步的收尾。 阶查找以常数概率返回正确的 $r$（相位估计加连分数的标准成功率）；若 $r=N-1$ 直接成功，若 $r<N-1$ 或者阶查找失败，就换一个新的 $a$ 重来。阶查找失败是独立随机事件，重复常数次即可把每轮的有效成功率垫高，渐近上只贡献对数因子（见第 6 节）。

4.1 阶查找黑盒：我们到底调用了什么

为了不把本词条变成 Shor 算法的复述，我们把量子阶查找当作黑盒使用，但黑盒的接口规格必须说清楚，因为算法的正确性与复杂度都挂在这些规格上。

为什么第 1 步要求 $\gcd (a,N)=1$。 阶查找的核心酉算子是模乘映射

$$U_a|x⟩=|ax\mathrm{mod}N⟩,x\in \{0,1,\dots ,N-1\}.$$

它要成为酉算子（即计算基上的置换），当且仅当 $a$ 在模 $N$ 下可逆，也就是 $\gcd (a,N)=1$：若 $a$ 可逆，$x\mapsto ax$ 有逆映射 $y\mapsto a^{-1}y$，因而是双射；反之若 $\gcd (a,N)=g>1$，则 $a\cdot (N/g)\equiv 0=a\cdot 0$，映射把两个不同的基矢送到同一个像，不是置换，更谈不上酉。所以 gcd 预筛选不仅抓出明显的合数，也保证喂给量子电路的输入合法。

黑盒内部做了什么（一句话版本）。 $U_a$ 保持 $r$ 维不变子空间 $\mathrm{span}\{|a^k⟩:k=0,\dots ,r-1\}$（$r={\mathrm{ord}}_N(a)$），在其上循环置换基矢，因此特征值是 $e^{2\pi is/r}$（$s=0,\dots ,r-1$）。相位估计把某个 $s/r$ 的近似值读到辅助寄存器，再用连分数展开从逼近值中恢复分母 $r$。细节见相位估计与 Shor 算法两课。

黑盒的输出规格。 相位估计读出的近似值以（近似）均匀分布落在 $\{s/r:s=0,\dots ,r-1\}$ 上；连分数展开能恢复出 $r$ 本身（而不是 $r$ 的因子）的条件是 $\gcd (s,r)=1$，其概率为 $\frac{\phi (r)}{r}$——用第 5 节将介绍的同一条下界，这至少是 $\Omega (1/\log \log r)$。所以单次运行直接给出 $r$ 的概率是 $\Omega (1/\log \log r)$，另有有界概率因相位估计精度不足而失败；独立重复 $O(\log \log r)=O(\log n)$ 次即可把每轮的成功率垫到常数。失败模式值得细看：测量到 $\gcd (s,r)>1$ 的 $s$ 时，连分数给出 $r$ 的真因子而非 $r$——但“$r=N-1$ 吗”这个判定问题对假阳性天然免疫：即使黑盒报错，只要我们核验 $a^{N-1}\equiv 1$（已是第 2 步的副产品）并且只接受 $r=N-1$ 这一个答案，错误的 $r$ 只会让我们白跑一轮，而不会让我们颁发错误证书。这一点与第 7 节“素数证书零假阳性”的论断互为表里。

黑盒的成本规格。 相位估计需要把相位读到约 $2n$ 位精度（连分数法要求误差小于 $\frac{1}{2r^2}\approx 2^{-2n}$ 才能唯一确定分母 $r$），因此要执行 $O(n)$ 个逐比特受控的模乘 $U_a^{2^j}$；每次模乘即一次 $n$ 位整数乘法加一次模约减。这个成本账在第 6 节展开。

5. 素数情形：为什么很快找到生成元

算法的期望运行时间取决于一个数论问题：当 $N$ 是素数时，随机 $a$ 有多大概率是生成元（即阶为 $N-1$）？答案依赖两件事：${\mathbb{Z}}_N^{\ast }$ 是循环群，以及循环群中生成元的精确计数。

5.1 素数时 ${\mathbb{Z}}_N^{\ast }$ 是循环群

$N$ 为素数时，模 $N$ 的剩余类构成域 ${\mathbb{F}}_N$，${\mathbb{Z}}_N^{\ast }$ 是它的乘法群。我们要证：

引理（域的乘法群的有限子群是循环群）。设 $G$ 是某个域的乘法群的有限子群，则 $G$ 是循环群。

证明的关键是多项式根的计数：域上 $d$ 次多项式至多有 $d$ 个根，所以对任何 $d\ge 1$，方程 $x^d=1$ 在 $G$ 中至多有 $d$ 个解。记 $m=|G|$，对每个 $d\mid m$，令

$$\psi (d)=\#\{x\in G:x\text{ 的阶恰为 }d\}.$$

逐步推出 $\psi$ 的形状：

• 若 $\psi (d)>0$，取一个阶为 $d$ 的元素 $h$。它的幂 $1,h,h^2,\dots ,h^{d-1}$ 互不相同（$h^i=h^j$ 蕴含 $h^{|i-j|}=1$，与阶为 $d$ 矛盾），且每一个都满足 $x^d=1$。这根方程至多有 $d$ 个解，所以 $x^d=1$ 的解恰好就是这 $d$ 个幂。
• 任何阶为 $d$ 的元素都满足 $x^d=1$，故必在 $\{1,h,\dots ,h^{d-1}\}$ 之中。其中 $h^k$ 的阶是 $d/\gcd (k,d)$（习题 4 证明这个标准事实），等于 $d$ 当且仅当 $\gcd (k,d)=1$。这样的 $k$ 恰有 $\phi (d)$ 个。
• 所以对每个 $d\mid m$，要么 $\psi (d)=0$，要么 $\psi (d)=\phi (d)$。

最后用 Euler 函数的经典恒等式

$$\sum _{d\mid m}\phi (d)=m$$

收尾（恒等式的证明：把 $\{1,\dots ,m\}$ 按 $d=\gcd (k,m)$ 分类，$\gcd (k,m)=d$ 等价于 $\gcd (k/d,m/d)=1$，所以第 $d$ 类恰有 $\phi (m/d)$ 个元素；$d$ 跑遍 $m$ 的因子时 $m/d$ 也跑遍 $m$ 的因子，求和即得）。一方面，$G$ 的 $m$ 个元素按各自的阶分类，给出 ${\sum }_{d\mid m}\psi (d)=m$；另一方面 $\psi (d)\le \phi (d)$ 且 ${\sum }_{d\mid m}\phi (d)=m$。两个和相等而逐项有上界，只能每项都取等：$\psi (d)=\phi (d)$ 对所有 $d\mid m$ 成立。特别地

$$\psi (m)=\phi (m)\ge 1,$$

即 $G$ 中存在阶为 $m$ 的元素——它就是生成元，$G$ 是循环群。Q.E.D.

这个证明还顺手给出了计数：阶为 $m$ 的循环群恰有 $\phi (m)$ 个生成元。

5.2 随机底数的成功概率

当 $N$ 为素数，${\mathbb{Z}}_N^{\ast }$ 是阶 $N-1$ 的循环群，由上面的计数，随机 $a$ 成功的概率是

$$p=\frac{\phi (N-1)}{N-1}.$$

$\phi (m)$ 可以小到多少？先看一个精确公式。Euler 函数是积性的（$\gcd (m_1,m_2)=1$ 时 $\phi (m_1{m}_2)=\phi (m_1)\phi (m_2)$，这是中国剩余定理的直接推论），且对素数幂有 $\phi (p^e)=p^e-p^{e-1}=p^e(1-\frac{1}{p})$（$p^e$ 个数里恰有 $p^{e-1}$ 个是 $p$ 的倍数，其余都与之互素）。于是对 $m={\prod }_i{p}_i^{e_i}$，

$$\frac{\phi (m)}{m}=\prod _{p\mid m}\left(1-\frac{1}{p}\right).$$

这个乘积只在 $m$ 拥有很多小素因子时才小：因子 $1-\frac{1}{2}$ 砍半，再乘 $1-\frac{1}{3}$、$1-\frac{1}{5}$……衰减得最厉害的情形是 $m$ 取前若干个素数的乘积（所谓的 primorial）。而前 $k$ 个素数的乘积大小约为 $e^{(1+o(1))k\log k}$，倒过来即 $k=O(\log m/\log \log m)$，代入 Mertens 定理（${\prod }_{p\le x}(1-\frac{1}{p})\approx \frac{e^{-\gamma }}{\log x}$）的尺度，$\phi (m)/m$ 的下坠速度只是对数对数级。解析数论据此给出如下粗略下界：对足够大的 $m$，

$$\frac{\phi (m)}{m}>\frac{1}{3\log \log m}.$$

我们不证明这条界（它属于解析数论的标准结果），但要会用它的含义：$\phi (m)/m$ 衰减得非常慢，只比 $1/\log \log m$ 略快。于是单次随机选取的成功概率 $p\ge \frac{1}{3\log \log (N-1)}$，独立重复选取时，由几何分布的期望，找到一个生成元所需的期望底数个数满足

$$\frac{1}{p}\le 3\log \log (N-1).$$

注意一个关键的尺度换算：$N$ 是 $n$ 位数，$N\le 2^n$，所以

$$\log \log (N-1)\le \log \log N\le \log n$$

（对数取什么底只影响常数因子）。因此期望只需 $O(\log \log N)=O(\log n)$ 个随机底数就能命中一个生成元。

给一个数量级感受：取 $n=1024$ 位的 $N$，自然对数下 $\ln \ln N\approx \ln (1024\ln 2)\approx \ln 710\approx 6.6$，所以期望尝试次数上界约为 $3\times 6.6\approx 20$ 个底数——量子阶查找是昂贵的，但它只需要被调用二十来次（期望值），而不是指数次。

想把“期望常数次成功”升级为“以 $1-\delta$ 的概率成功”，用 $(1-p{)}^k\le e^{-kp}\le \delta$ 解出

$$k\ge \frac{1}{p}\ln \frac{1}{\delta }=O\left(\log \log N\cdot \log \frac{1}{\delta }\right);$$

取 $\delta$ 为逆多项式（如 $\delta =1/n$），$\log \frac{1}{\delta }=O(\log n)$，这就是“重复 $O(\log n)$ 次把错误压到逆多项式”的来源，我们在第 6 节把它组装进总复杂度。

6. 复杂度逐项分析

现在把每个部件的成本摆出来。记 $n=\lceil {\log }_{2}N\rceil$。

• 第 1 步（gcd）：辗转相除法对 $n$ 位整数做 $O(n)$ 轮带余除法，每轮朴素实现 $O(n^2)$ 比特操作，合计 $O(n^2)$。这不是瓶颈。
• 第 2 步（预筛选模幂）：快速幂把 $a^{(N-1)/2}\mathrm{mod}N$ 分解为 $O(n)$ 次模乘（指数有 $n$ 位，每位移最多一次平方、一次乘法）。用普通整数乘法电路每次模乘 $O(n^2)$ 门，合计 $O(n^3)$ 经典门。
• 第 4 步（量子阶查找）：这是主成本，值得把账拆细。相位估计需要把相位读到约 $2n$ 位精度（连分数法要求误差小于 $\frac{1}{2r^2}$ 而 $r<N\le 2^n$），因此指数寄存器用 $O(n)$ 个比特，逐比特施加受控的 $U_a^{2^j}$（$j=0,1,\dots ,O(n)$）。这里有一个标准省法：$U_a^{2^j}$ 不必靠“把 $U_a$ 做 $2^j$ 次”来实现——经典预处理算出常数 $a_j=a^{2^j}\mathrm{mod}N$（反复平方 $j$ 次即得），于是 $U_a^{2^j}=U_{a_j}$ 就是一次普通的受控模乘。所以量子部分总共 $O(n)$ 个受控模乘；每次模乘即一次 $n$ 位整数乘法加一次模约减，用普通整数乘法电路为 $O(n^2)$ 门，乘起来是 $O(n^3)$；最后对指数寄存器做一次逆 QFT，成本 $O(n^2)$，被吸收。合计约 $\tilde{O}(n^3)$ 门。
• 底数个数：第 5 节算出期望 $O(\log \log N)=O(\log n)$ 个。
• 错误放大：把整个流程重复 $O(\log n)$ 次，把“不走运没碰到生成元”以及阶查找自身的常数失败率一并压到逆多项式。

逐项相乘：每次量子阶查找 $\tilde{O}(n^3)$，乘以期望底数个数 $O(\log n)$，再乘以错误放大的 $O(\log n)$，得到 Donis-Vela—Garcia-Escartin 口径下的总复杂度

$$O(n^3(\log n{)}^2).$$

如果底层整数乘法不用朴素电路，而采用渐近快速乘法（Harvey 与 van der Hoeven 证明两个 $n$ 位整数可以在 $O(n\log n)$ 时间内相乘，Zoo 398），每次模乘从 $O(n^2)$ 降到 $\tilde{O}(n)$，每次阶查找相应地从 $\tilde{O}(n^3)$ 降到约 $\tilde{O}(n^2)$，代入同样的底数个数与放大因子，总复杂度可降至接近

$$O(n^2(\log n{)}^3\log \log n).$$

必须强调原文的保留条款：这些式子是门操作的渐近估计，不能省略模乘电路、容错开销或成功率放大。具体来说，大 $O$ 记号吞掉了模乘电路的常数因子；真实机器上运行还需要容错编码带来的巨大物理比特开销；而“期望 $O(\log n)$ 个底数”说的是期望，严格的尾概率界要靠上面的放大论证。比较两个复杂度表达式时，比较的只是渐近增长阶。

7. 合数分支与证书类型

算法的输出要按分支分类讨论，这是理解“量子素性证明”概念的关键。

确定性的合数证据。 若算法在第 1 步找到 $\gcd (a,N)>1$，或在第 2 步找到 Fermat 见证 / $1$ 的非平凡平方根，合数结论可以经典核验：验算一次 gcd、一次模幂或一次乘法即可。这类输出是零误差的。

概率性的合数判断。 若算法跑了很多轮，既没有找到合数见证，也没有找到阶为 $N-1$ 的元素，我们只能宣布“$N$ 大概是合数”。这不是确定性证书：素数也可能因为抽样不走运而暂时没有命中生成元（概率 $(1-p{)}^k$）。第 5 节的估计说明，重复 $O(\log n)$ 次可把这类错误降到逆多项式，再按需要继续放大——但它本质上是 Monte Carlo 式的判断，与“找到生成元”那种一锤定音的认证地位不同。素数证书零假阳性；“多次未找到”仍是概率性判断。

把放大账算清楚：设单轮（含一次阶查找）“找到生成元”的成功概率至少为 $q$（$q$ 由底数命中概率 $p$ 与阶查找自身的常数成功率相乘得到，仍是 $\Omega (1/\log n)$ 量级）。$k$ 轮全部失败的概率是 $(1-q{)}^k\le e^{-kq}$；要它不超过 $\delta$，解 $e^{-kq}\le \delta$ 得 $k\ge \frac{1}{q}\ln \frac{1}{\delta }$。取 $\delta =n^{-c}$（逆多项式），$\ln \frac{1}{\delta }=c\ln n$，于是 $k=O(\log n\cdot \log n)$ 轮封顶——这正是第 6 节总复杂度里两个 $\log n$ 因子的最终归宿。若还想压到 $\delta =2^{-n}$ 量级，$\ln \frac{1}{\delta }=O(n)$，代价相应变为 $O(n\log n)$ 轮，渐近上仍只是多项式。

两种素数证书的对比。 当算法找到生成元 $a$ 时，$(N,a)$ 是一份“量子可验证证书”：任何拥有量子计算机的验证者重新运行阶查找，确认 ${\mathrm{ord}}_N(a)=N-1$，即可被说服。但它不像带有 $N-1$ 完整分解的 Lucas—Pratt 证书那样可由纯经典验证者快速核验——这是少做分解换来的代价。Chau—Lo 路线多做一次完整分解，换回经典可核验性；直接阶查找路线省下分解，验证者也需要量子设备。选用哪一种，取决于“证书给谁看”。

最后摆正量子方法的位置：量子素性测试并不意味着经典素性测试无效。素性判定早已被证明在 P 中（AKS）；量子改进针对的是特定操作模型和渐近次数。本词条的核心教学价值，是展示“阶”这个 Shor 算法内部的对象，本身就可以作为正向的素性证书——量子计算在这里省掉的不是“判定素性”这个任务，而是“分解 $N-1$”这次过度的努力。

8. 三种素性证明路线的取舍

到这里我们已经见到了三条路线，把它们并排摆在一起，取舍就清楚了。

经典 Lucas—Pratt 路线。 不分解 $N-1$ 就无法开始；而分解一般整数没有已知的多项式时间经典算法。一旦（以某种方式）拿到分解，证书递归、零假阳性、纯经典可核验，核验只做 $O(n)$ 次模幂。瓶颈完全在“分解 $N-1$”这一步上。

经典判定算法（AKS、ECPP）。 AKS 是无条件的确定性多项式时间判定，回答了理论问题，但它输出的是“是/否”而非可独立核验的证书，且实际常数并不占优；ECPP 在实践中高效且输出经典可核验的证书，但其复杂度分析依赖启发式假设（这是模型依赖的保留条款：启发式成立与否不影响单次证书核验的正确性，只影响运行时间的严格上界）。这些工作与量子路线并不冲突——它们说明经典世界已经把“判定”解决得很好，量子路线的卖点在别处。

Chau—Lo 路线（量子分解 + 经典证书）。 用 Shor 算法分解 $N-1$ 的渐近成本与分解 $N$ 相当（同样是模幂与 QFT 的组合），换来一份 Lucas—Pratt 型证书：验证者只需要经典计算机。适合“证明一次、到处张贴”的场景——证书发布给没有能力或没有意愿运行量子设备的验证者群体。

直接阶查找路线（本词条）。 不分解任何东西，只对候选底数做阶查找；证书 $(N,a)$ 由量子验证者重跑阶查找来核验。省掉的是对 $N-1$ 的完整分解：分解要处理所有因子、处理幂次、还要对因子递归判定素性，而 Lucas 条件只需要一个元素的阶。换来的是验证者也必须是量子的。

一句话总结：证书越“经典可核验”，前期要做的量子/数论工作越多；证书越“轻”，验证者的门槛越高。 选哪条路线，取决于证书要交给谁、以及分解 $N-1$ 在你的参数区间里到底有多贵。

9. 小例子：$N=7$ 与 $N=15$ 完整演算

9.1 $N=7$：一次成功的认证

取 $N=7$，$N-1=6=2\cdot 3$。我们模拟算法，先看一个会走进死胡同的底数，再看一个成功的。

底数 $a=2$。 第 1 步：$\gcd (2,7)=1$，通过。第 2 步：

$$z=2^{(7-1)/2}=2^3=8\equiv 1(\mathrm{mod}7).$$

$z=1$，落入第 3 步：${\mathrm{ord}}_7(2)\mid 3$，阶至多为 $3$，丢弃。（确实 $2^3\equiv 1$，阶就是 $3$。）

底数 $a=3$。 第 1 步：$\gcd (3,7)=1$。第 2 步：

$$z=3^3=27\equiv 6\equiv -1(\mathrm{mod}7).$$

$z=-1$，进入第 4 步调用阶查找。我们把阶查找会返回的结果手工算出来，逐个幂：

$$\begin{array}{rl}{3}^1& \equiv 3,\\ 3^2& =9\equiv 2,\\ 3^3& =3\cdot 3^2\equiv 3\cdot 2=6,\\ 3^4& \equiv 3\cdot 6=18\equiv 4,\\ 3^5& \equiv 3\cdot 4=12\equiv 5,\\ 3^6& \equiv 3\cdot 5=15\equiv 1(\mathrm{mod}7).\end{array}$$

前五个幂都不是 $1$，第六个是 $1$，所以 ${\mathrm{ord}}_7(3)=6=N-1$。第 5 步：由 Lucas 定理，$7$ 是素数，输出证书 $(7,3)$。

顺便用第 3 节的经典 Lucas 检验复核这份证书：已知 $6=2\cdot 3$，检查 $3^6\equiv 1$（上面已算）、$3^{6/2}=3^3\equiv 6\not\equiv 1$、$3^{6/3}=3^2\equiv 2\not\equiv 1$，两个素因子都通过——阶确实是 $6$。这也演示了经典核验需要知道 $6=2\cdot 3$ 这个分解，而量子路线不需要。

再注意 $a=6$ 的情形：$6\equiv -1$，$z=6^3=(6^2)\cdot 6\equiv 1\cdot 6\equiv -1$，会进入第 4 步，但 ${\mathrm{ord}}_7(6)=2\ne 6$。这说明 $z=-1$ 只是“候选”，第 4 步的量子阶查找是必不可少的裁判（习题 3 展开这一点）。

最后把 ${\mathbb{Z}}_7^{\ast }$ 的完整阶谱列出来，验证第 5 节的计数公式。六个元素的阶分别是

$${\mathrm{ord}}_7(1)=1,{\mathrm{ord}}_7(2)=3,{\mathrm{ord}}_7(3)=6,{\mathrm{ord}}_7(4)=3,{\mathrm{ord}}_7(5)=6,{\mathrm{ord}}_7(6)=2,$$

其中 ${\mathrm{ord}}_7(5)=6$ 由 $5\equiv -2$、$5^2\equiv 4$、$5^3\equiv -1$、$5^6\equiv 1$ 逐步验得（$5^3\equiv -1$ 说明阶整除 $6$ 但不整除 $3$，又不整除 $2$，只能是 $6$）。阶为 $6$ 的元素恰有 $3$ 和 $5$ 两个，数目等于 $\phi (6)=2$，与“阶为 $m$ 的循环群恰有 $\phi (m)$ 个生成元”一致。随机底数命中生成元的概率是 $\frac{\phi (6)}{6}=\frac{1}{3}$，期望 $3$ 次尝试——上面我们试了 $a=2$（丢弃）、$a=3$（成功），正好两次，与期望同量级。

9.2 $N=15$：为什么永远不会出错误证书

取 $N=15$。先算 $\phi (15)$：$15=3\cdot 5$，由 Euler 函数的乘性（$\gcd (3,5)=1$）

$$\phi (15)=\phi (3)\phi (5)=2\cdot 4=8,$$

确实 ${\mathbb{Z}}_{15}^{\ast }=\{1,2,4,7,8,11,13,14\}$ 共 $8$ 个元素。由 Lagrange 定理，任何单位的阶都整除 $8$，而证书要求阶等于 $N-1=14$——$14\nmid$……更直接地说，$14>8$，$8$ 的因子中没有 $14$，所以任何 $a$ 的阶都不可能等于 $14$，算法永远不会对 $15$ 产生素数证书。这正是 Lucas 定理逆方向的体现：合数不存在阶 $N-1$ 的元素。

再看两个底数在算法中的实际走向。

底数 $a=2$。 第 1 步：$\gcd (2,15)=1$。第 2 步：

$$z=2^7\mathrm{mod}15.$$

快速幂：$2^2=4$，$2^4=16\equiv 1$，所以 $2^7=2^4\cdot 2^2\cdot 2\equiv 1\cdot 4\cdot 2=8$。$z=8\notin \{1,14\}$，落入第 2 步的合数分支。验证：$2^{14}=(2^4{)}^3\cdot 2^2\equiv 4\not\equiv 1(\mathrm{mod}15)$，$a=2$ 是 Fermat 见证，$15$ 被确定证伪。顺带看到 ${\mathrm{ord}}_{15}(2)=4$（$2^4\equiv 1$ 且更小的正幂 $2,4,8$ 都不是 $1$），与“阶整除 $\phi (15)=8$”一致。

底数 $a=4$（演示非平凡平方根分支）。 $\gcd (4,15)=1$；$4^2=16\equiv 1$，所以 ${\mathrm{ord}}_{15}(4)=2$。第 2 步：

$$z=4^7=(4^2{)}^3\cdot 4\equiv 4(\mathrm{mod}15).$$

$z=4\notin \{1,14\}$，但 $z^2=4^2\equiv 1$：这是 $1$ 的非平凡平方根情形。按第 4 节的分析，$\gcd (z-1,N)=\gcd (3,15)=3$ 直接给出 $15$ 的非平凡因子——合数结论不仅成立，还附带了一份分解证据。

10. 小结与习题

本词条的要点：

• Fermat 条件只限制 $a^{N-1}$，会被 Carmichael 数整体欺骗；Lucas 条件要求完整阶等于 $N-1$，是素数的充要认证。
• 经典 Lucas—Pratt 证书把困难转移到分解 $N-1$；Chau—Lo 用 Shor 算法补上这块短板，证书经典可核验。
• 直接阶查找（Donis-Vela—Garcia-Escartin）绕过了先分解 $N-1$ 的步骤：预筛选（gcd 与 $z=a^{(N-1)/2}$）挑出候选者，量子阶查找一锤定音。
• 素数时随机底数以概率 $\phi (N-1)/(N-1)\ge 1/(3\log \log (N-1))$ 命中生成元，期望 $O(\log \log N)=O(\log n)$ 次尝试。
• 总复杂度 $O(n^3(\log n{)}^2)$（普通乘法），采用渐近快速乘法时接近 $O(n^2(\log n{)}^3\log \log n)$；这些是渐近门估计，不含容错开销。
• 素数证书零假阳性；“多次未找到”仍是概率性判断。必须说明证书由经典验证者还是量子验证者核验。

习题。

1.（基础）补全 Lucas 定理证明的细节：证明若 ${\mathrm{ord}}_N(a)=N-1$，则 $\phi (N)=N-1$；并说明若 $N$ 是合数，为什么 $\phi (N)\le N-2$。 2.（计算）找出模 $11$ 的全部生成元，并验证其数目等于 $\phi (10)$。（提示：先验证 $2$ 是生成元，再用“$g^k$ 是生成元当且仅当 $\gcd (k,10)=1$”。） 3.（理解）解释为什么 $a^{(N-1)/2}\equiv -1(\mathrm{mod}N)$ 推出 ${\mathrm{ord}}_N(a)\mid N-1$ 与 ${\nu }_2({\mathrm{ord}}_N(a))={\nu }_2(N-1)$，但不保证阶就是 $N-1$。用第 9 节 $N=7$、$a=6$ 的例子说明：为什么第 4 步的量子阶查找不能省。 4.（证明）设 $g$ 是阶为 $m$ 的循环群的生成元，证明 $\mathrm{ord}(g^k)=m/\gcd (k,m)$，并由此推出阶为 $m$ 的循环群恰有 $\phi (m)$ 个生成元。 5.（推导）由 $p\ge \frac{1}{3\log \log (N-1)}$ 出发，推导找到一个生成元所需的期望底数个数上界；说明为什么 $\log \log N=O(\log n)$；再把每次阶查找 $\tilde{O}(n^3)$、底数个数与 $O(\log n)$ 次错误放大组装成总复杂度 $O(n^3(\log n{)}^2)$。 6.（讨论）比较“输出 $N-1$ 的因子分解”（Chau—Lo）和“输出一个生成元 $a$”（直接阶查找）两种证书的核验资源：各自的验证者需要什么设备、做多少次什么运算？什么场景下前者的额外分解是值得的？

参考文献

• Zoo 编号 396：Alvaro Donis-Vela 与 Juan Carlos Garcia-Escartin, A Quantum Primality Test with Order Finding.
• Zoo 编号 397：H. F. Chau 与 H.-K. Lo, Primality Test via Quantum Factorization.
• Zoo 编号 393—395：Qi Cheng、Daniel J. Bernstein、François Morain 关于 AKS/ECPP 素性证明复杂度的经典工作。
• Zoo 编号 398：David Harvey 与 Joris van der Hoeven, Integer Multiplication in Time $O(n\log n)$.
• Zoo 编号 399 是 Quantum Algorithm Zoo 记录的一条个人通信，不作为可独立核验的技术依据。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch09-algebra-number-theory/primality-proving
• 内容遵循 CC BY-NC-SA 4.0 许可协议