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

技術要約：六角形3-smooth族における無条件原始的証明

問題提起
本論文は、中心六角数（centered hexagonal numbers）の特定のパラメータ化された部分族である $p = 3m(m + 1) + 1$ （ここで $m = 2^a 3^b - 1$、整数 $a, b \ge 1$）に対する無条件の素数判定証明（primality certification）を扱う。Pocklington–Lehmerの判定法は、$p-1$ の完全分解された約数 $F > \sqrt{p}$ を提示することで、一般的な大きな整数に対して実用的な素数証明の経路を提供するが、課題は各素因数 $q$ に対する適切な「証拠（witnesses）」となる基数 $w_q$ を見つけることにある。この特定の族において、約数 $F = 2^a 3^{b+1}$ は完全に分解されており、無条件に $F > \sqrt{p}$ を満たす。しかし、固定された証拠（具体的には $w_2=5$ および $w_3=7$）の妥当性は、これまで経験則的に観察されていたものの、厳密かつ決定論的な特徴付けが欠けていた。本論文は、これらの固定された証拠が普遍的なものか否か、そしてもしそうでない場合は、その妥当性のための正確な条件を提示することを目的としている。

手法
著者らは、代数数論と初等的な算術篩（ふるい）を組み合わせて用いている：

1. Pocklington–Lehmerの枠組み： 証明は、$p$ が素数であるための条件として、証拠 $w_2, w_3$ が存在し、$w_q^{(p-1)/q} \not\equiv 1 \pmod p$ かつ $\gcd(w_q^{(p-1)/q}-1, p) = 1$ となることに依拠している。$p \equiv 1 \pmod 6$ であるため、これは $w_2$ が二次非剰余であり、$w_3$ が三次非剰余であることを確認することに帰着する。
2. 平方剰余： $w_2 = 5$ の妥当性は、ルジャンドル記号 $\left(\frac{5}{p}\right)$ を用いて分析され、$m = 2^a 3^b - 1$ のパラメータを通じた $a$ および $b$ の性質へと関連付けられる。
3. アイゼンシュタイン整数における三次剰余： $w_3 = 7$ の妥当性は、$\mathbb{Z}[\omega]$（ここで $\omega = e^{2\pi i/3}$）における三次剰余記号を用いて分析される。著者らは、$p = (m+1)^3 - m^3 = \pi \bar{\pi}$ という明示的な分解を利用して、アイゼンシュタインの三次剰余律を適用している。これにより、$w_3=7$ の $p$ 係の三次剰余性を、$m \pmod 7$ に関する条件へと簡約することが可能となる。
4. 算術フィルタ： 高コストな大きな数の算術計算を行う前に、候補となる数を排除するための3つの初等的なフィルタを導出している：
   • 6を法とする恒等式（自動的に成立）。
   • $(-3)$ 二次剰余篩（$q \equiv 2 \pmod 3$ の素数を排除）。
   • $(a \pmod 3, b \pmod 6)$ の剰余類に基づく、法7の禁止クラス・テスト。

主な貢献
本論文は、経験則的な仮定を決定論的な規則に置き換える2つの厳密な定理を提供している：

• 定理 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-smoothの制約なし）へと拡張し、$m \pmod{21}$ に基づく三次剰余性を特徴付けている。

結果

• フィルタの効率性： 法7のフィルタと $(-3)$ 篩の組み合わせにより、大きな数の算術（ミラー・ラビンやPocklingtonの検証）を実行する前に、候補となるペア $(a, b)$ の約87%を排除している。
• 計算による実証： マルチコア実装（"PrimeQuest"）により、コンシューマー向けハードウェア上で4つの無条件素数証明を生成した。最大の証明は、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が常に機能するか」というこの族における未解決の問いを解決し、「5と7は常に機能するわけではない」ことを証明した上で、この不確実性を正確な剰余条件へと置き換えた。
• 控えめな主張： 著者らは、本論文は「古典的な未解決問題を解決するものではない」と述べている。29,998桁の素数は、一般的な基準では記録（一般的な用途のECPPはより大きな数を扱う）ではないが、汎用的なハードウェアにおける本フレームワークの効率性を実証するものである。
• 認識論的地位： すべての理論的主張（定理 4.1, 4.5, 4.7 およびフィルタ）は厳密かつ無条件である。計算結果は厳密な算術によって検証されている。本研究は、先行する解析理論のフォローアップとして提示されており、Pocklington法が完全に決定論的かつ最小限となる特定の3-smooth部分族を孤立させて抽出している。