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

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

## 1. 从 Fermat 条件到乘法阶

设 $N>2$ 为奇数，

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

是模 $N$ 的单位群，大小为 Euler 函数 $\varphi(N)$。元素 $a$ 的乘法阶定义为

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

Lagrange 定理给出

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

若 $N$ 为素数，则 $\varphi(N)=N-1$，Fermat 小定理保证 $a^{N-1}\equiv1\pmod N$。反方向一般不成立：Carmichael 数可让所有单位都通过 Fermat 检验。Lucas 的关键观察更强：

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

证明很短。元素阶整除群阶，所以 $N-1\le\varphi(N)$；另一方面恒有 $\varphi(N)\le N-1$，故 $\varphi(N)=N-1$。这只可能在 $N$ 为素数时发生。

## 2. 为什么经典 Lucas 证书要分解 $N-1$

若已知

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

则可以验证

$$
a^{N-1}\equiv1\pmod N,
\qquad
a^{(N-1)/p_i}\not\equiv1\pmod N
$$

对每个不同素因子 $p_i$ 成立。这证明 $a$ 的阶含有 $N-1$ 的每个素数幂，因而阶就是 $N-1$。困难从“求 $N$ 的因子”转移成“分解 $N-1$”。Pratt 证书递归附上各 $p_i$ 的素性证书，使核验完全经典。

Chau--Lo 方法直接用 Shor 算法分解 $N-1$，再构造这类证书。优点是输出可由经典计算机核验；代价是执行了完整分解，而判定 Lucas 条件其实只需要知道一个元素的阶。

## 3. 直接阶查找算法

令 $n=\lceil\log_2N\rceil$。一次迭代如下：

1. 均匀选择 $1<a<N$，计算 $g=\gcd(a,N)$。若 $g>1$，直接输出非平凡因子，确定 $N$ 为合数。
2. 经典计算 $z=a^{(N-1)/2}\bmod N$。若 $z\notin\{1,-1\}$，则 $a^{N-1}\not\equiv1$，$a$ 是合数见证。
3. 若 $z=1$，则 $\operatorname{ord}_N(a)\le(N-1)/2$，丢弃该 $a$。
4. 若 $z=-1$，调用 Shor 的量子阶查找得到 $r=\operatorname{ord}_N(a)$。
5. 若 $r=N-1$，由 Lucas 定理确定 $N$ 为素数；否则换一个 $a$。

预筛选不是正确性所必需，却避免对明显无用的底数调用昂贵量子电路。$z=-1$ 还保证 $a^{N-1}=1$ 且 $r\mid N-1$，所以阶查找结果有明确的比较目标。

## 4. 素数时为什么很快找到生成元

当 $N$ 为素数，$\mathbb Z_N^*$ 是阶 $N-1$ 的循环群。一个阶为 $m$ 的循环群恰有 $\varphi(m)$ 个生成元，因此随机 $a$ 成功的概率是

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

对足够大的 $m$ 有粗略下界

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

所以期望只需 $O(\log\log N)=O(\log n)$ 个随机底数。每次阶查找通过模指数酉算子与 QFT 恢复 $r$，用普通整数乘法电路约需 $\widetilde O(n^3)$ 门。Donis-Vela--Garcia-Escartin 的口径给出总复杂度

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

采用渐近快速乘法时可降至接近

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

这些式子是门操作的渐近估计，不能省略模乘电路、容错开销或成功率放大。

## 5. 合数分支与证书类型

若算法找到 $\gcd(a,N)>1$ 或 Fermat/Euler 见证，合数结论可经典核验。若只是多次没有找到阶 $N-1$ 的元素，则结果是**概率性合数判断**，不是确定性证书；素数也可能因抽样不走运而暂时失败。重复 $O(\log n)$ 次可把这类错误降到逆多项式，再按需要放大。

当算法找到生成元 $a$ 时，$(N,a)$ 是“量子可验证证书”：验证者重新运行阶查找即可确认 $\operatorname{ord}_N(a)=N-1$。它不像带有 $N-1$ 完整分解的 Lucas--Pratt 证书那样可由纯经典验证者快速核验。这是少做分解换来的代价。

量子素性测试也不意味着经典素性测试无效。素性判定早已在 P 中；量子改进针对特定操作模型和渐近次数，核心教学价值是展示“阶”本身可作为正向证书。

## 6. 例子：$N=7$ 与 $N=15$

对 $N=7$ 取 $a=3$：

$$
3^1,3^2,\ldots,3^6\equiv3,2,6,4,5,1\pmod7,
$$

所以 $\operatorname{ord}_7(3)=6=N-1$，立即证明 7 为素数。

对 $N=15$，$\varphi(15)=8$。任何单位的阶都整除 8，不可能等于 $14$；因此算法永远不会产生错误的素数证书。比如 $a=2$ 时

$$
2^4\equiv1\pmod{15},
$$

阶仅为 4。

## 7. 小结与习题

- Fermat 条件只限制 $a^{N-1}$，Lucas 条件要求完整阶等于 $N-1$。
- 量子阶查找绕过了先分解 $N-1$ 的步骤。
- 素数证书零假阳性；“多次未找到”仍是概率性判断。
- 必须说明证书由经典验证者还是量子验证者核验。

1. 证明若 $\operatorname{ord}_N(a)=N-1$，则 $\varphi(N)=N-1$。
2. 找出模 11 的全部生成元，并验证数目等于 $\varphi(10)$。
3. 解释为什么 $a^{(N-1)/2}=-1$ 推出 $\operatorname{ord}_N(a)\mid N-1$，但不保证阶就是 $N-1$。
4. 比较“输出 $N-1$ 的因子分解”和“输出一个生成元 $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 记录的一条个人通信，不作为可独立核验的技术依据。