素数证明书（综述）

贡献者： 待更新

　　 本文根据 CC-BY-SA 协议转载翻译自维基百科相关文章。

　　 在数学和计算机科学中，素数证明书或素性证明是指一种简洁、形式化的证明，用来表明一个数是质数。素数证明书的作用是：无需运行代价高昂或不够可靠的素数判定算法，就能快速验证一个数的素性。这里的 “简洁” 通常意味着，该证明的规模至多是这个数位数的多项式倍（例如，如果该数有 $b$ 位二进制数位，证明可能大约包含 $b^2$ 位）。

　　 素数证明书直接表明了以下结论：素数判定问题，以及其补问题——整数分解的补集问题——属于 NP 类（即给出解后可在多项式时间内验证的问题类）。这些问题显然也属于 co-NP 类。这是首次有力的证据表明这些问题并不是 NP 完全的，因为如果它们是 NP 完全的，就意味着 NP 是 co-NP 的子集，而这一结论被广泛认为是错误的；事实上，这也是当时首次展示了一个已知属于 NP ∩ co-NP 但不知是否属于 P 类 的问题。

　　 对于其补问题（证明一个数是合数）的证明书，生成方法非常直接：只需给出一个非平凡因子即可。标准的概率型素数判定算法（如 Baillie–PSW 素数判定法、费马素数检验、米勒–拉宾素数检验）在输入是合数的情况下，也会生成 “合数证明书”，但对于质数输入则不会生成证明书。

1. 普拉特证明书

　　 素数证明书这一概念最早是由 普拉特证明书引入的，该方法由 Vaughan Pratt 于 1975 年提出 \(^\text{[1]}\)。他描述了这种证明书的结构，并证明了它的规模是多项式级的，而且可以在多项式时间内完成验证。普拉特证明书基于卢卡斯素性检验，该检验本质上是费马小定理的逆命题，并附加了一个条件使其成立：

　　 卢卡斯定理：假设存在一个整数 $a$，使得：

• $a^{n - 1} \equiv 1 \pmod{n}$，
• 对于 $n - 1$ 的每个质因数 $q$，都有 $a^{(n - 1) / q} \not\equiv 1 \pmod{n}$，

　　 那么 $n$ 是质数。

　　 给定这样的 $a$（称为见证，witness）以及 $n - 1$ 的质因数分解，我们可以很快验证上述条件：只需做线性数量的模指数运算（因为任何整数的质因子数不会超过它的比特数）。每次模指数运算可以通过平方乘法在 $O(\log n)$ 次乘法中完成（见大 O 符号）。

　　 即便采用最基础的 “学校式” 整数乘法，总耗时也只有 $O((\log n)^{4})$；如果使用 David Harvey 和 Joris van der Hoeven 提出的目前已知渐进时间最优的乘法算法，则可以将其降低到 $O((\log n)^{3} \log\log n)$，使用软 O 符号则记作 $\tilde{O}((\log n)^{3})$。

　　 然而，如果在给出 $n - 1$ 的 “质因数分解” 时掺入合数，就有可能欺骗验证者，让其错误地接受一个合数为质数。例如，假设我们声称 $n = 85$ 是质数，并提供 $a = 4$ 以及 $n - 1 = 6 \times 14$ 作为它的 “质因数分解”。那么（取 $q = 6$ 和 $q = 14$）：

• $4$ 与 $85$ 互素；
• $4^{85-1} \equiv 1 \pmod{85}$；
• $4^{(85-1)/6} \equiv 16 \pmod{85}$，$4^{(85-1)/14} \equiv 16 \pmod{85}$。

　　 这样我们会错误地得出结论：85 是质数。我们当然不希望仅仅为了防止这种欺骗就强迫验证者去重新分解质因数，因此更好的办法是：为 $n - 1$ 的每个质因子也提供相应的素数证明书，这些只是原问题规模更小的实例。如此递归下去，直到遇到一个已知为质数的数（例如 2）为止。最终，我们得到一个质数树，每个质数节点都关联着一个见证 $a$。例如，以下是数 229 的完整 普拉特证明书：

• $229$（$a = 6$，$229 - 1 = 2^2 \times 3 \times 19$）
• $2$（已知质数）
• $3$（$a = 2$，$3 - 1 = 2$）
• $2$（已知质数）
• $19$（$a = 2$，$19 - 1 = 2 \times 3^2$）
• $2$（已知质数）
• $3$（$a = 2$，$3 - 1 = 2$）
• $2$（已知质数）

　　 这个证明树最多包含 $4\log_{2}n - 4$ 个除 2 以外的值，这可以通过一个简单的归纳证明得到（基于 Pratt 定理 2）。该结论对 $3$ 成立；一般情况下，取 $p > 3$，令它在证明树中的子节点为 $p_1, \dots, p_k$。根据归纳假设，以 $p_i$ 为根的子树至多包含 $ 4\log_{2}p_i - 4$ 个值，因此整个树包含的值最多为： $$ 1 + \sum_{i=1}^{k} \big(4\log_{2}p_i - 4\big) = -4k + 4\log_{2}(p_1 \cdots p_k) \leq 4\log_{2}p - 4~ $$ 由于 $k \ge 2$，且 $p_1 \cdots p_k = p - 1$。

　　 因为每个值最多有 $\log n$ 位，所以这也表明该证明书的大小为 $O((\log n)^2)$ 位。由于除 2 之外的值有 $O(\log n)$ 个，并且每个值的验证最多需要一次模幂运算（而模幂运算是运行时间的主要消耗），因此总运行时间为： $$ O\big((\log n)^3(\log \log n)(\log \log \log n)\big) \quad \text{或} \quad \tilde{O}((\log n)^3)~ $$ 这对于计算数论学者通常处理的数值范围来说是相当可行的。

　　 然而，尽管理论上很有用且容易验证，实际为 $n$ 生成一个 Pratt 证明书需要分解 $n - 1$ 以及其他可能很大的数。对于一些特殊的数（如费马质数）来说，这很简单，但对于一般形式的大质数，目前生成 Pratt 证明书的难度远大于直接进行质数判定。

2. 阿特金–戈德瓦瑟–基利安–莫兰证明书

　　 为了解决大数高效生成质数证明书的问题，1986 年 Shafi Goldwasser 和 Joe Kilian 提出了一种基于椭圆曲线理论的新型证明书 \(^\text{[2]}\)。随后，A. O. L. Atkin 和 François Morain 以此为基础，发展出 Atkin–Goldwasser–Kilian–Morain 证明书，它们正是椭圆曲线质数证明系统生成和验证的证明书类型 \(^\text{[3]}\)。

　　 就像 Pratt 证明书基于 Lucas 定理一样，Atkin–Goldwasser–Kilian–Morain 证明书基于 Goldwasser 和 Kilian 的以下定理（出自 Almost All Primes Can Be Quickly Certified 一文的引理 2）：

　　 定理：假设我们有：

• 一个不被 2 或 3 整除的正整数 $n$；
• $M_x, M_y, A, B \in \mathbb{Z}_n$（模 $n$ 的整数），满足 $M_y^2 = M_x^3 + A M_x + B$ 且 $4A^3 + 27B^2$ 与 $n$ 互素；
• 一个质数 $q > n^{1/2} + 1 + 2n^{1/4}$。

　　 那么 $M = (M_x, M_y)$ 是椭圆曲线 $y^2 = x^3 + A x + B$ 上的一个非单位元点。设 $kM$ 表示利用标准椭圆曲线加法将 $M$ 自加 $k$ 次。如果 $qM$ 是单位元 $I$，则 $n$ 为质数。

　　 严格来说，椭圆曲线只能在域上构造，而 $\mathbb{Z}_n$ 只有在 $n$ 为质数时才是域，因此这看起来像是在假设我们要证明的结论。困难之处在于椭圆曲线加法算法需要在域中求逆，而在 $\mathbb{Z}_n$ 中可能不存在逆元。然而，可以证明（见 Almost All Primes Can Be Quickly Certified 的引理 1），如果我们只是像曲线在域上定义那样进行计算，并且在任何一步都不去求一个没有逆元的元素的逆，那么结果依然有效；如果过程中遇到一个没有逆元的元素，这就说明 $n$ 是合数。

　　 从该定理推导证明书的方法 是：首先编码 $M_x, M_y, A, B$ 和 $q$，然后递归地对 $q < n$ 进行质数性证明的编码，直到得到一个已知的质数为止。该证明书的大小为 $O((\log n)^2)$，验证时间为 $O((\log n)^4)$。

　　 此外，可以证明生成这些证明书的算法在除去极少数质数外，对绝大多数质数的期望运行时间是多项式级的，并且这些例外质数的比例会随着质数规模的增大而指数级下降。因此，它非常适合生成带有证明的大型随机质数，这一应用在密码学中尤为重要，例如用于生成可被形式证明有效的 RSA 密钥。

3. Pocklington 基于证明的证明书

　　 基于 Pocklington 定理（参见 Pocklington 素性检验）变体的可证明质数生成方法 \(^\text{[4]}\)，可以成为一种高效的生成质数的技术（其代价通常低于概率型生成方法），并且具有内置质数证明书这一额外优势。虽然这些质数看起来像是某类 “特殊质数”，但需要注意的是，每一个质数整数都可以通过基于 Pocklington 的可证明生成算法生成。

4. Pocklington 素性检验

　　 设 $P = Rh + 1$ 其中 $R = \prod q_j^{e_j}$ 且 $q_j$ 为互不相同的质数，$e_j$ 为大于零的整数，并且存在一个见证元 $g$，使得：

1. $g^{Rh} \equiv 1 \pmod{P}$
2. $\gcd\big(g^{Rh/q_j} - 1 \pmod{P},\; P\big) = 1$ 对所有的 $q_j$ 都成立。

　　 那么，如果以下条件之一成立，则 $P$ 为质数：

　　 a)（见文献 \(^\text{[5]}\)）$R \geq h$ 或等价于 $R > P^{1/2}$

　　 b)（见文献 \(^\text{[6]}\)：推论 1）$R \geq h^{1/2}$ 或等价于 $R > P^{1/3}$

　　 并且存在整数

• $$ a \equiv h \pmod{R}, \quad 0 \leq a < R~ $$ $$ b = \frac{h - a}{R}~ $$
• 使得 $(a - 4b) \neq 0$ 且存在一个大于 2 的小质数 $r$，使得 $(a - 4b)^{r/2} \not\equiv 1 \pmod{r}$

Pocklington 素性证明证书

　　 一个 Pocklington 素性证明证书包含以下内容：质数 $P$、一组整除 $(P-1)$ 的质数 $q_j$，这些 $q_j$ 中的每一个要么附有其自身的 Pocklington 素性证明证书，要么足够小到可以直接视为已知质数，以及一个见证元 $g$。

　　 该证书所需的比特数（以及计算代价的量级）大约为：对于版本 (b)： $$ \log_{2} P \left( 1 + \sum_{k=1}^{\infty} \frac{1}{3^k} \right) = 1.5 \log_{2} P~ $$ 对于版本 (a)： $$ \log_{2} P \left( 1 + \sum_{k=1}^{\infty} \frac{1}{2^k} \right) = 2 \log_{2} P~ $$

一个小例子

　　 设 $P = 1056893$ 注意：$P - 1 = 1621 \cdot 163 \cdot 2^{2}$ 并且 $P^{1/2} = 1028.053\ldots, \quad P^{1/3} = 101.86156\ldots$

• 使用见证元 $g = 2$，方程 (1) 得到满足，同时在方程 (2) 中使用 $q = 163$ 与 $q = 1621$ 也满足条件。
• 对于版本 a，证书只需：$P = 1056893, \quad q = 1621, \quad g = 2$
• 对于版本 b，证书只需：$P = 1056893, \quad q = 163, \quad g = 2$
• 但还需要做一些额外工作：$h = (1056893 - 1)/163 = 6484$
• $a \equiv h \equiv 127 \pmod{163}$ 和 $b = (6484 - 127)/163= 39$
• 使用 $r = 3$ 时失败： $$ \left(127^2 - 4 \cdot 39\right)^{(3-1)/2} \equiv (1^2 - 0)^{1} \equiv 1 \pmod{3}~ $$
• 使用 $r = 5$ 时成功： $$ \left(127^2 - 4 \cdot 39\right)^{(5-1)/2} \equiv (2^2 - 1)^2 \equiv 2 \pmod{5}~ $$ 因此，$P$ 为质数。

5. “PRIMES 属于 P 类” 的影响

　　 “PRIMES 属于 P 类”\(^\text{[7]}\) 是理论计算机科学领域的一项突破性成果。该论文由 Manindra Agrawal、Nitin Saxena 和 Neeraj Kayal 于 2002 年 8 月发表，证明了著名的 “判断一个数是否为质数” 这一问题可以在多项式时间内以确定性方式解决。作者因此在 2006 年获得了哥德尔奖和富尔克森奖。

　　 由于现在可以利用 AKS 素性测试在多项式时间内确定性地完成素性检验，一个质数本身就可以被视为其素性的 “证书”。该测试的运行时间为 $\tilde{O}((\log n)^6)$。在实际应用中，这种验证方法的开销比验证 Pratt 证书更大，但它不需要进行任何计算来生成证书本身。

6. 参考文献

1. Vaughan Pratt. 《每个质数都有一个简洁的证明证书》, SIAM 计算学报, 第 4 卷, 第 214–220 页, 1975 年。
2. Shafi Goldwasser, Joe Kilian. 《几乎所有质数都可以被快速验证》, 第 18 届 STOC 会议论文集, 第 316–329 页, 1986 年。
3. A. O. L. Atkin, François Morain. 《椭圆曲线与素性证明》 (PDF), 计算数学, 第 61 卷 (第 203 期): 29–68 页, 1993 年。doi:10.1090/s0025-5718-1993-1199989-x。
4. Henry C. Pocklington. 《利用费马定理判断大数的质合性质》, 剑桥哲学学会会刊, 第 18 卷: 29–30 页, 1914–1916 年。
5. Richard Crandall, Carl Pomerance. 《质数：一种计算的视角》（第 2 版）, 施普林格出版社, 2005 年，美国纽约第五大道 175 号。
6. John Brillhart, D. H. Lehmer, J. L. Selfridge. 《新的素性判别标准与 $2^m \pm 1$ 的分解》 (PDF), 计算数学, 第 29 卷 (第 130 期): 620–647 页, 1975 年 4 月。doi:10.1090/S0025-5718-1975-0384673-1。
7. Manindra Agrawal, Neeraj Kayal, Nitin Saxena. 《PRIMES 属于 P 类》 (PDF), 数学年刊, 第 160 卷 (第 2 期): 781–793 页, 2004 年 9 月。doi:10.4007/annals.2004.160.781。

7. 外部链接

• MathWorld：素性证明证书
• MathWorld：普拉特证书
• MathWorld：阿特金–戈德瓦瑟–基利安–莫兰证书
• 质数词汇表：素性证明证书
• Vašek Chvátal，《普拉特素性证明讲义》，计算机科学系，罗格斯大学。PDF 版本可在康考迪亚大学获取。