Unconditional Primality Certificates for the Hexagonal 3-smooth Family p = 3m(m+1) + 1: Deterministic Pocklington Witnesses and Arithmetic Filters

技术摘要：六角形 3-光滑族的不变原性证明证书

问题陈述
本文研究了针对特定参数化中心六角数子族的无条件素性认证问题，该族定义为 $p = 3m(m + 1) + 1$，其中 $m = 2^a 3^b - 1$ 且整数 $a, b \ge 1$。虽然 Pocklington–Lehmer 判别法通过展示 $p-1$ 的一个完全分解因子 $F > \sqrt{p}$，为证明一般大整数的素性提供了一条实用的路径，但挑战在于为 $F$ 的每个素因子 $q$ 寻找合适的“见证者”（witnesses, 基数 $w_q$）。对于这个特定的族，$F = 2^a 3^{b+1}$ 是完全分解的，并且无条件满足 $F > \sqrt{p}$。然而，固定见证者（具体为 $w_2=5$ 和 $w_3=7$）的有效性此前仅在启发式层面被观察到，缺乏严谨的、确定性的特征描述。本文旨在解决这些固定见证者是否具有普适性，若非如此，则提供其有效性的精确条件。

方法论
作者结合了代数数论和初等算术筛法：

1. Pocklington–Lehmer 框架： 证明依赖于以下判别法：若存在见证者 $w_2, w_3$ 使得 $w_q^{(p-1)/q} \not\equiv 1 \pmod p$ 且 $\gcd(w_q^{(p-1)/q}-1, p) = 1$，则 $p$ 为素数。由于 $p \equiv 1 \pmod 6$，这简化为检查 $w_2$ 是否为二次非剩余，以及 $w_3$ 是否为三次非剩余 $\pmod p$。
2. 二次互反律： 通过使用 Legendre 符号 $\left(\frac{5}{p}\right)$ 来分析 $w_2 = 5$ 的有效性，并通过 $m = 2^a 3^b - 1$ 的性质将其与参数 $a$ 和 $b$ 联系起来。
3. 艾森斯坦整数中的三次互反律： 利用 $\mathbb{Z}[\omega]$（其中 $\omega = e^{2\pi i/3}$）中的三次剩余符号来分析 $w_3 = 7$ 的有效性。作者利用显式分解 $p = (m+1)^3 - m^3 = \pi \bar{\pi}$ 来应用爱森斯坦的三次互反律。这使得将 $7 \pmod p$ 的三次剩余性简化为对 $m \pmod 7$ 的条件。
4. 算术过滤器： 作者推导了三个初等过滤器，用于在进行昂贵的大数运算前排除非素数候选者：
   • 一个模 6 同余恒等式（自动满足）。
   • 一个 $(-3)$ 二次剩余筛法（排除素数 $q \equiv 2 \pmod 3$）。
   • 一个基于 $(a \pmod 3, b \pmod 6)$ 剩余类的模 7 禁止类测试。

主要贡献
本文提供了两个严谨的定理，用确定性规则取代了启发式假设：

• 定理 4.1 (见证者 $w_2=5$)： 基数 5 是有效的 Pocklington 见证者，当且仅当 $a - b \equiv 1, 2 \pmod 4$。如果该条件不成立，则 5 是二次剩余，必须选择不同的见证者。
• 定理 4.5 (见证者 $w_3=7$)： 基数 7 是有效的 Pocklington 见证者，当且仅当 $m \not\equiv 2 \pmod 7$。该条件等价于 $(a \pmod 3, b \pmod 6) \notin \{(0, 1), (1, 5), (2, 3)\}$。
• 确定性选择规则： 推论 4.9 将这些结果综合为一个完整的算法，用于选择见证者。如果固定见证者未能通过同余检查，算法会确定性地选择最小的二次或三次非剩余，从而确保认证过程是可证明正确的，而非依赖于偶然性。
• 推广： 命题 4.7 将对 7 的三次特征的分析扩展到了更广泛的族 $p = 3m^2 + 3m + 1$（不带 3-光滑约束），根据 $m \pmod{21}$ 对其三次剩余性进行了表征。

结果

• 过滤器效率： 结合模 7 过滤器和 $(-3)$ 筛法，在进行任何大数运算（Miller–Rabin 或 Pocklington 验证）之前，即可排除约 87% 的候选对 $(a, b)$。
• 计算演示： 一个多核实现（"PrimeQuest"）在消费级硬件上生成了四个无条件素性证书。最大的证书对应一个 29,998 位十进制数字 的素数（$m = 2^{19435}3^{19173} - 1$）。
• 验证： 该 29,998 位数字的素数已通过独立验证。该证书满足 $w_2=5$ 和 $w_3=7$ 的 Pocklington 条件，且边际值 $2 \log_2 F - \log_2 p \approx 1.58$ 比特确认了其无条件素性。

意义与范围
本文明确将自身的贡献界定为结构性与显式性，而非打破纪录：

• 解决启发式问题： 它解决了关于“5 和 7 是否总是对该族有效”这一开放性问题，证明了它们并非总是有效，并用精确的同余条件取代了这种不确定性。
• 适度的声明： 作者指出本文“未解决任何经典的开放问题”。虽然 29,998 位的素数按通用标准来看并不算纪录（通用的 ECPP 可以处理更大的数字），但它展示了该框架在普通商用硬件上的高效性。
• 认识论地位： 所有理论主张（定理 4.1、4.5、4.7 及过滤器）都是严谨且无条件的。计算结果通过精确算术进行了验证。这项工作被呈现为对先前解析理论的后续研究，隔离出了一个使 Pocklington 方法变得完全确定且极简化的特定 3-光滑子族。