# 量子素性证明：用阶为 $N-1$ 的元素认证素数

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

阅读本课前，我们假设你已经学过[量子傅里叶变换](../ch03-algo-basics/quantum-fourier-transform.md)、[相位估计](../ch03-algo-basics/phase-estimation.md)与 [Shor 算法](../ch04-classic-algorithms/shors-algorithm-tutorial.md)。本课不再重复推导阶查找电路本身，而是把它当作一个可以调用的黑盒：输入单位 $a$ 与模数 $N$，输出 $\operatorname{ord}_N(a)$。我们要回答的问题是：**为什么知道一个元素的乘法阶，就能证明 $N$ 是素数？量子计算机在这里到底省掉了哪一步？**

:::{admonition} 本课知识点
:class: tip

1. **[素性判定与素性证明的分野](#primality-testing-vs-certificates)**——能区分“概率性判定”与“可核验证书”两条主线，并用 $561=3\times11\times17$ 解释 Carmichael 数为何能让所有底数通过 Fermat 检验。
2. **[单位群、乘法阶与 Lucas 定理](#unit-group-order-lucas)**——能写出 $\mathbb Z_N^*$、$\varphi(N)$ 与 $\operatorname{ord}_N(a)$ 的定义，由 Lagrange 定理推导 $\operatorname{ord}_N(a)\mid\varphi(N)$，并逐步证明 Lucas 定理。
3. **[经典 Lucas--Pratt 证书](#lucas-pratt-certificate)**——能解释已知 $N-1$ 的分解后两组同余条件为何足以确定 $\operatorname{ord}_N(a)=N-1$，并核验 $N=7$ 的递归证书树。
4. **[直接阶查找算法与预筛选](#order-finding-algorithm)**——能列出算法的五个步骤，解释 $z=a^{(N-1)/2}$ 各分支的正确性论证，并说明为何只有 $z=-1$ 分支值得调用量子阶查找。
5. **[循环性、生成元计数与成功概率](#cyclic-group-generators)**——能证明域的乘法群的有限子群是循环群，推出阶为 $m$ 的循环群恰有 $\varphi(m)$ 个生成元，并计算随机底数的命中概率与期望尝试次数。
6. **[复杂度逐项分析](#complexity-breakdown)**——能逐项核算 gcd、预筛选模幂、量子阶查找与错误放大的成本，推导总复杂度 $O(n^3(\log n)^2)$，并说明快速乘法带来的改进。
7. **[合数分支与证书类型](#certificate-types)**——能区分确定性合数证据与概率性的“多次未找到”判断，解释“素数证书零假阳性”，并比较量子可验证证书与经典可核验证书。
8. **[三种素性证明路线的取舍](#route-tradeoffs)**——能比较经典 Lucas--Pratt、AKS/ECPP、Chau--Lo 与直接阶查找路线的输出形式与验证者资源，说明“证书给谁看”如何决定选择。

:::

(primality-testing-vs-certificates)=
## 1. 问题的来龙去脉：素性判定与素性证明

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

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

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

$$
a^{560}\equiv1\pmod3,\qquad a^{560}\equiv1\pmod{11},\qquad a^{560}\equiv1\pmod{17},
$$

三个同余式模数两两互素，由中国剩余定理合并得 $a^{560}\equiv1\pmod{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）。本课的主线就是把这个观察讲透。

(unit-group-order-lucas)=
## 2. 数论准备：单位群、乘法阶与 Lucas 定理

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

$$
\mathbb Z_N^*=\{a\in\{1,\ldots,N-1\}:\gcd(a,N)=1\},
$$

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

$$
\varphi(N)=|\mathbb Z_N^*|=\#\{1\le k\le N-1:\gcd(k,N)=1\}.
$$

元素 $a\in\mathbb Z_N^*$ 的**乘法阶 (multiplicative order)** 定义为

$$
\operatorname{ord}_N(a)=\min\{r>0:a^r\equiv1\pmod N\},
$$

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

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

$$
\operatorname{ord}_N(a)\mid\varphi(N).
$$

若 $N$ 为素数，则 $1,\ldots,N-1$ 全部与 $N$ 互素，$\varphi(N)=N-1$，于是 $\operatorname{ord}_N(a)\mid N-1$；特别地 $a^{N-1}\equiv1\pmod N$，这正是 Fermat 小定理。

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

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

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

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

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

(lucas-pratt-certificate)=
## 3. 经典 Lucas 证书：为什么绕不开分解 $N-1$

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

设已知

$$
N-1=\prod_i p_i^{e_i},
$$

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

$$
a^{N-1}\equiv1\pmod N,\qquad a^{(N-1)/p_i}\not\equiv1\pmod N\ \text{对每个 }i.
$$

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

- 由第一个条件，$r\mid N-1$（阶的基本性质：$a^m=1\iff\operatorname{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}\equiv1\pmod N$——与第二个条件矛盾。
- 所以对所有 $i$ 都有 $f_i=e_i$，即 $r=N-1$。Q.E.D.

核验的代价：每个条件是一次模幂，指数约 $n=\lceil\log_2N\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\cdot3$；
- 子证书 1：$p_1=2$，$2$ 是素数（递归基例，直接承认）；
- 子证书 2：$p_2=3$，见证元 $a'=2$，分解 $3-1=2$（再次落到基例）。

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

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

(order-finding-algorithm)=
## 4. 直接阶查找算法

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

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

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

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

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

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

**第 3 步为什么安全。** $z=a^{(N-1)/2}\equiv1$ 意味着阶整除 $(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}\neq1$，所以只能等于 $-1$（这里用到 $N$ 为素数时 $\mathbb Z_N^*$ 中 $1$ 的平方根只有 $\pm1$；若 $N$ 是合数，这个 $a$ 反正也不是我们要的）。换句话说，**预筛选永远不会误删真正的生成元**。

**第 4 步为什么值得调用量子计算机。** $z=-1$ 同时告诉我们两件事：(i) $a^{N-1}=z^2=1$，所以 $\operatorname{ord}_N(a)\mid N-1$；(ii) $\operatorname{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\rangle=|ax\bmod N\rangle,\qquad x\in\{0,1,\ldots,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)\equiv0=a\cdot0$，映射把两个不同的基矢送到同一个像，不是置换，更谈不上酉。所以 gcd 预筛选不仅抓出明显的合数，也保证喂给量子电路的输入合法。

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

**黑盒的输出规格。** 相位估计读出的近似值以（近似）均匀分布落在 $\{s/r:s=0,\ldots,r-1\}$ 上；连分数展开能恢复出 $r$ 本身（而不是 $r$ 的因子）的条件是 $\gcd(s,r)=1$，其概率为 $\frac{\varphi(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}\equiv1$（已是第 2 步的副产品）并且只接受 $r=N-1$ 这一个答案，错误的 $r$ 只会让我们白跑一轮，而不会让我们颁发错误证书。这一点与第 7 节“素数证书零假阳性”的论断互为表里。

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

(cyclic-group-generators)=
## 5. 素数情形：为什么很快找到生成元

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

### 5.1 素数时 $\mathbb Z_N^*$ 是循环群

$N$ 为素数时，模 $N$ 的剩余类构成域 $\mathbb F_N$，$\mathbb Z_N^*$ 是它的乘法群。我们要证：

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

证明的关键是**多项式根的计数**：域上 $d$ 次多项式至多有 $d$ 个根，所以对任何 $d\ge1$，方程 $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,\ldots,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,\ldots,h^{d-1}\}$ 之中。其中 $h^k$ 的阶是 $d/\gcd(k,d)$（练习 5 第 3 题证明这个标准事实），等于 $d$ 当且仅当 $\gcd(k,d)=1$。这样的 $k$ 恰有 $\varphi(d)$ 个。
- 所以对每个 $d\mid m$，要么 $\psi(d)=0$，要么 $\psi(d)=\varphi(d)$。

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

$$
\sum_{d\mid m}\varphi(d)=m
$$

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

$$
\psi(m)=\varphi(m)\ge1,
$$

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

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

### 5.2 随机底数的成功概率

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

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

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

$$
\frac{\varphi(m)}{m}=\prod_{p\mid m}\left(1-\frac1p\right).
$$

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

$$
\frac{\varphi(m)}{m}>\frac1{3\log\log m}.
$$

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

$$
\frac1p\le3\log\log(N-1).
$$

注意一个关键的尺度换算：$N$ 是 $n$ 位数，$N\le2^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\ln2)\approx\ln710\approx6.6$，所以期望尝试次数上界约为 $3\times6.6\approx20$ 个底数——量子阶查找是昂贵的，但它只需要被调用二十来次（期望值），而不是指数次。

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

$$
k\ge\frac1p\ln\frac1\delta=O\!\left(\log\log N\cdot\log\frac1\delta\right);
$$

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

(complexity-breakdown)=
## 6. 复杂度逐项分析

现在把每个部件的成本摆出来。记 $n=\lceil\log_2N\rceil$。

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

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

$$
O\bigl(n^3(\log n)^2\bigr).
$$

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

$$
O\bigl(n^2(\log n)^3\log\log n\bigr).
$$

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

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

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

(route-tradeoffs)=
## 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\cdot3$。我们模拟算法，先看一个会走进死胡同的底数，再看一个成功的。

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

$$
z=2^{(7-1)/2}=2^3=8\equiv1\pmod7.
$$

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

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

$$
z=3^3=27\equiv6\equiv-1\pmod7.
$$

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

$$
\begin{aligned}
3^1&\equiv3,\\
3^2&=9\equiv2,\\
3^3&=3\cdot3^2\equiv3\cdot2=6,\\
3^4&\equiv3\cdot6=18\equiv4,\\
3^5&\equiv3\cdot4=12\equiv5,\\
3^6&\equiv3\cdot5=15\equiv1\pmod7.
\end{aligned}
$$

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

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

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

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

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

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

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

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

$$
\varphi(15)=\varphi(3)\varphi(5)=2\cdot4=8,
$$

确实 $\mathbb Z_{15}^*=\{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\bmod{15}.
$$

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

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

$$
z=4^7=(4^2)^3\cdot4\equiv4\pmod{15}.
$$

$z=4\notin\{1,14\}$，但 $z^2=4^2\equiv1$：这是 $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}$）挑出候选者，量子阶查找一锤定音。
- 素数时随机底数以概率 $\varphi(N-1)/(N-1)\ge1/(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【素性判定与素性证明的分野】**（→ [第 1 节](#primality-testing-vs-certificates)）

1. 写出 Fermat 小定理的结论，并说明通过 $k$ 轮 Miller--Rabin 检验后得到的是“误把合数认成素数的概率不超过 $(1/4)^k$”式的概率保证，而不是一份可核验的证明。
2. 仿照正文的论证，解释为什么任何满足 $\gcd(a,561)=1$ 的底数都必然通过 Fermat 检验；再指出哪类底数会在第 4 节算法的第 1 步（gcd 检查）处直接暴露 $561$ 的因子。

> 提示：$a$ 模 $3$、$11$、$17$ 的阶分别整除 $2$、$10$、$16$，而它们都整除 $560$；最后用中国剩余定理合并。

**练习 2【单位群、乘法阶与 Lucas 定理】**（→ [第 2 节](#unit-group-order-lucas)）

1. 列出 $\mathbb Z_{15}^*$ 的全部元素并计算 $\varphi(15)$，再求出 $\operatorname{ord}_{15}(2)$。
2. 补全 Lucas 定理证明的细节：证明若 $\operatorname{ord}_N(a)=N-1$，则 $\varphi(N)=N-1$；并说明若 $N$ 是合数，为什么 $\varphi(N)\le N-2$。

> 提示：合数 $N$ 的最小素因子 $p$ 满足 $1<p<N$，它落在 $\{1,\ldots,N-1\}$ 中且与 $N$ 不互素。

**练习 3【经典 Lucas--Pratt 证书】**（→ [第 3 节](#lucas-pratt-certificate)）

1. 已知 $10=2\cdot5$，写出经典 Lucas 检验验证 $\operatorname{ord}_{11}(2)=10$ 所需的全部同余式，并逐条算出数值。
2. 解释为什么不知道 $N-1$ 的分解时，直接验证 $\operatorname{ord}_N(a)=N-1$ 要花指数时间；并说明 Pratt 证书如何通过递归附上每个 $p_i$ 的子证书，使整棵树的核验保持多项式时间。

> 提示：比较“对每个素因子做一次模幂”与“逐一检查 $a^1,\ldots,a^{N-2}$”的次数；递归在 $p_i=2$ 处终止。

**练习 4【直接阶查找算法与预筛选】**（→ [第 4 节](#order-finding-algorithm)）

1. 对 $N=15$、$a=2$ 执行算法第 1、2 步：计算 $\gcd(2,15)$ 与 $z=2^7\bmod15$，指出落入哪个分支、得出什么结论。
2. 对 $N=15$、$a=4$：算出 $z=4^7\bmod15$，验证 $z$ 是 $1$ 的非平凡平方根，并用 $\gcd(z-1,N)$ 提取 $15$ 的一个非平凡因子。
3. 解释为什么 $a^{(N-1)/2}\equiv-1\pmod N$ 推出 $\operatorname{ord}_N(a)\mid N-1$ 与 $\nu_2(\operatorname{ord}_N(a))=\nu_2(N-1)$，但不保证阶就是 $N-1$。用第 9 节 $N=7$、$a=6$ 的例子说明：为什么第 4 步的量子阶查找不能省。

> 提示：$6\equiv-1\pmod7$，所以 $\operatorname{ord}_7(6)=2\ne6$。

**练习 5【循环性、生成元计数与成功概率】**（→ [第 5 节](#cyclic-group-generators)）

1. 列出 $\mathbb Z_7^*$ 中六个元素各自的阶，数出其中阶为 $6$ 的元素个数，并与 $\varphi(6)$ 比较。
2. 找出模 $11$ 的全部生成元，并验证其数目等于 $\varphi(10)$。（提示：先验证 $2$ 是生成元，再用“$g^k$ 是生成元当且仅当 $\gcd(k,10)=1$”。）
3. 设 $g$ 是阶为 $m$ 的循环群的生成元，证明 $\operatorname{ord}(g^k)=m/\gcd(k,m)$，并由此推出阶为 $m$ 的循环群恰有 $\varphi(m)$ 个生成元。

> 提示：记 $d=\gcd(k,m)$，证明 $m\mid kt\iff\frac{m}{d}\mid t$。

**练习 6【复杂度逐项分析】**（→ [第 6 节](#complexity-breakdown)）

1. 核算第 2 步预筛选模幂的成本：说明为什么快速幂只需 $O(n)$ 次模乘，用普通乘法电路合计为 $O(n^3)$ 经典门。
2. 由 $p\ge\frac{1}{3\log\log(N-1)}$ 出发，推导找到一个生成元所需的期望底数个数上界；说明为什么 $\log\log N=O(\log n)$；再把每次阶查找 $\widetilde O(n^3)$、底数个数与 $O(\log n)$ 次错误放大组装成总复杂度 $O(n^3(\log n)^2)$。

> 提示：期望底数个数是 $1/p$；由 $N\le2^n$ 得 $\log\log N\le\log n+O(1)$。

**练习 7【合数分支与证书类型】**（→ [第 7 节](#certificate-types)）

1. 列出算法的三类输出（确定性的合数证据、素数证书、概率性的“多次未找到”），并各写出一个核验所需的运算与核验者类型。
2. 论证“素数证书零假阳性”：结合阶查找黑盒的失败模式（连分数只会把阶恢复成真阶的因子或报失败），说明为什么只要核验 $a^{N-1}\equiv1\pmod N$ 且只接受 $r=N-1$，算法不可能把合数认成素数。

> 提示：$N$ 为合数时任何元素的阶都 $\le\varphi(N)\le N-2<N-1$。

**练习 8【三种素性证明路线的取舍】**（→ [第 8 节](#route-tradeoffs)）

1. 分别用一句话概括经典 Lucas--Pratt、AKS/ECPP、Chau--Lo 与直接阶查找路线的输出形式，并标注核验各需要经典设备还是量子设备。
2. 比较“输出 $N-1$ 的因子分解”（Chau--Lo）和“输出一个生成元 $a$”（直接阶查找）两种证书的核验资源：各自的验证者需要什么设备、做多少次什么运算？什么场景下前者的额外分解是值得的？

> 提示：从“证书会被核验多少次、核验者是否拥有量子设备”两个维度权衡。

## 参考文献

- Zoo 编号 396：Alvaro Donis-Vela 与 Juan Carlos Garcia-Escartin, [A Quantum Primality Test with Order Finding](https://arxiv.org/abs/1711.02616).
- Zoo 编号 397：H. F. Chau 与 H.-K. Lo, [Primality Test via Quantum Factorization](https://arxiv.org/abs/quant-ph/9508005).
- 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)$](https://hal.science/hal-02070778).
- Zoo 编号 399 是 Quantum Algorithm Zoo 记录的一条个人通信，不作为可独立核验的技术依据。