A primality test for $Kp^n+1$ numbers and a generalization of Safe Primes and Sophie Germain Primes

技術要約：$Kp^n + 1$ 型数の素数判定法、およびセーフ素数とソフィ・ジェルマン素数の一般化

問題提起
本論文は、$p$ を素数とし $K < p^n$ である整数 $N = Kp^n + 1$ の素数性を判定するという計算上の課題に取り組んでいる。フェルマーの素数判定法（$a^{N-1} \equiv 1 \pmod N$）は計算コストが低いものの、確定的ではなく、それ単体では素数であることを証明するには不十分である。プロスの定理（$N=K2^n+1$ の場合）やポクロトンの定理といった既存の決定論的手法は、多くの場合、最大公約数（GCD）の計算や、円分多項式 $\Phi_p$ に関する複雑な条件の検証を必要とする。著者は、これらの要件を簡略化する方法、具体的には GCD 計算を必要とせず、単一のモジュロ冪乗に依存する判定法を目指している。また、これらの概念を拡張し、セーフ素数やソフィ・ジェルマン素数に類似した新しい素数の族を定義し、分析することを目的としている。

手法
本論文は、要素の $N$ を法とする位数に関する数論的補題、および $Ap+1$ 型の整数の割り切れる性質を用いている。

1. プロスの定理の一般化： 著者は、$Ap+1$が$Dp+1$で割り切れることに関する補題、および$N$ を法とする要素の位数と、その素因数の関係に関する補題を証明している。これらは新しい素数判定基準を導出するために使用される。
2. 確率論的およびヒューリスティックな分析： 新たに定義された素数族の分布については、ハーディとリトルウッドの予想B、および積分推定を用いて、これらの素数の密度をモデル化している。著者は、理論的な漸近推定値と、特定の区間における素数の実測数を比較している。
3. 計算による検証： 提案された分布推定の正確性をテストするため、様々な桁数（小さな数から10,000桁までの数）の素数を用いて広範な計算を行っている。

主な貢献と結果

• $Kp^n + 1$ に対する簡略化された素数判定法：

  • 定理 2.3： $N = Kp^n + 1$ （ただし $p^n \ge K$）に対する素数判定法を提供している。これは、(i) $a^{Kp^n-1} \equiv L \not\equiv 1 \pmod N$ および (ii) $L^p \equiv 1 \pmod N$ という2つの条件のみを必要とする。これにより、従来の一般化（例：Grauら、2015年）で必要とされていた GCD 計算が排除される。
  • 定理 2.5： パラメータ $j$ ($0 \le j \le n-1$) を許容するさらなる一般化であり、これにより素数であることを証明できる基数 $a$ の数を増加させる。
  • 定理 3.1 および 3.4： 特定の $j$ および $n$ の範囲（例：$p^j \ge p^{n-j} \ge (N-1)^{1/3}$）に対する追加の判定法を提供する。これらの条件により、より大きな $j$ の値が可能となり、ランダムに選ばれた基数 $a$ が素数判定条件を満たす確率が高まり、結果として素数の証明が成功する可能性が高まる。
  • 系： 本論文は、特定の無限個の整数の族（例：$N = 2Kp^2 + 1$ および $N = 2Kp^3 + 1$）を特定しており、$K$ と $p$ に関する特定の境界が満たされる場合、フェルマーの条件 $a^{N-1} \equiv 1 \pmod N$ を検証するだけで素数性を証明できることを示している。

• セーフ素数およびソフィ・ジェルマン素数の一般化：

  • 定義 4.1 ($a$-セーフ素数)： 素数 $N = 2Kp + 1$は、$2K < \log_a(2Kp+1)$を満たすとき、$a$-セーフ素数と定義される。これにより、$N-1$の素因数$p$ が他のどの因子よりも十分に大きいことが保証され、古典的なセーフ素数の特性を反映している。
  • $a$-ソフィ・ジェルマン素数 ($a$-SGP) の定義： 素数 $p$ は、$2Kp+1$が共に素数となるような$K$が少なくとも一つ存在し、かつ$2K < \log_a(2Kp+1)$を満たすとき、$a$-SGP と定義される。
  • 分布分析： 論文では、$a$-セーフ素数のカウントに関する漸近公式（$\alpha_1, \alpha_2$）、および与えられた素数が $a$-SGP である確率の推定値（$\alpha_3, \alpha_4, \alpha_5$）を導出している。
  • 分布に関する予想： 10,000桁までの素数を用いた計算に基づき、著者は以下を提唱している：
    • 予想 5.1： 与えられた素数 $p$ が 2-ソフィ・ジェルマン素数である確率は、$p \to \infty$ において約 0.76 に収束する。
    • 予想 5.2： $a$-SGP に関する上記の一般化であり、確率は $a$ に依存する極限値に収束することを示唆している。

• 経験的な知見：

  • 論文では、2-セーフ素数および 2-ソフィ・ジェルマン素数の実際のカウントと、提案された漸近推定値を比較した表を提示している。結果は、非常に大きな数（100桁から10,000桁）においても高い精度を示している。
  • 著者はこれらの知見をメルセンヌ素数に適用し、最初の30個のメルセンヌ素数のうち21個が 2-ソフィ・ジェルマン素数であることを特定し、推定値の有用性を検証した。
  • 最大既知の素数（$2^{82,589,933}-1$）が 2-ソフィ・ジェルマン素数である確率は、約 0.7637 と推定される。

意義
本論文は、$Kp^n + 1$ 型の族に対して、厳密性を維持しつつ GCD ステップを取り除くことで、既存の素数判定法よりも計算が容易な代替手段を提供すると主張している。さらに、セーフ素数およびソフィ・ジェルマン素数の一般化された枠組みを導入し、極めて大きな整数に対しても堅牢に見える、それらの分布に関する統計的モデルを提示している。著者は、これらの結果が暗号目的の大きな素数の生成や、特定の構造的特性を持つ素数の分布を理解するために有用であると考えている。本研究は、確立された数論（プロス、ポクロト、ハーディ・リトルウッド）に依拠し、それらを新しい補題を通じて拡張したものである。