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

技术摘要：针对 $Kp^n + 1$ 型数的素性测试及其对安全素数与索菲·热尔曼素数的推广

问题陈述
本文解决了确定形式为 $N = Kp^n + 1$ 的整数（其中 $p$ 为素数且 $K < p^n$）之素性的计算挑战。虽然费马素性测试（$a^{N-1} \equiv 1 \pmod N$）在计算上非常廉价，但它是概率性的，不足以单独用于证明素性。现有的确定性方法，如 Proth 定理（针对 $N=K2^n+1$）和 Pocklington 定理，通常需要计算最大公约数（GCD）或验证涉及分圆多项式 $\Phi_p$ 的复杂条件。作者寻求一种简化这些要求的方案，具体目标是实现一种依赖于单次模幂运算、无需 GCD 计算的测试方法，并扩展这些概念以定义和分析类似于安全素数（Safe Primes）和索菲·热尔曼素数（Sophie Germain Primes）的新型素数族。

方法论
本文利用了关于模 $N$ 下元素阶以及 $Ap+1$ 型数整除性质的数论引理。

1. Proth 定理的推广： 作者证明了关于 $Ap+1$能被$Dp+1$整除以及$N$ 的元素的阶与其素因子之间关系的引理。这些引理被用于推导新的素性判别准则。
2. 概率与启发式分析： 对于新定义的素数族的分布，本文利用 Hardy 和 Littlewood 的猜想 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$。这消除了以往推广方法（如 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$-SafePrimes)： 将素数 $N = 2Kp + 1$定义为$a$-安全素数，如果$2K < \log_a(2Kp+1)$。这确保了$N-1$的素因子$p$ 显著大于任何其他因子，体现了经典安全素数的特性。
  • $a$-索菲·热尔曼素数 ($a$-SGP) 的定义： 若存在至少一个满足 $2K < \log_a(2Kp+1)$ 的 $K$，使得 $2Kp+1$也是素数，则称素数$p$为$a$-SGP。
  • 分布分析： 本文推导了用于计算 $a$-安全素数计数的渐近公式（$\alpha_1, \alpha_2$），以及估计给定素数为 $a$-SGP 的概率（$\alpha_3, \alpha_4, \alpha_5$）。
  • 关于分布的猜想： 基于对高达 10,000 位数的计算，作者提出了：
    • 猜想 5.1： 当 $p \to \infty$ 时，给定素数 $p$ 是 2-索菲·热尔曼素数的概率收敛于约 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 步骤。此外，它引入了一个广义的安全素数和索菲·热尔曼素数框架，为它们的分布提供了一个统计模型，该模型对于极大的整数似乎也是稳健的。作者认为这些结果对于生成用于密码学的大型素数以及理解具有特定结构特征的素数分布具有重要价值。这项工作依赖于成熟的数论（Proth, Pocklington, Hardy-Littlewood），并通过新的引理和经验验证对其进行了扩展。