量子素性证明：用阶为 \(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\)”两种证书的核验资源。

参考文献