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

Resumen Técnico: Una prueba de primalidad para números de la forma $Kp^n + 1$ y una generalización de los primos seguros y los primos de Sophie Germain

Planteamiento del problema
El artículo aborda el desafío computacional de determinar la primalidad de enteros de la forma $N = Kp^n + 1$, donde $p$ es un primo y $K < p^n$. Aunque la prueba de primalidad de Fermat ($a^{N-1} \equiv 1 \pmod N$) es computacionalmente económica, es probabilística e insuficiente para certificar la primalidad por sí sola. Los métodos deterministas existentes, como el teorema de Proth (para $N=K2^n+1$) y el teorema de Pocklington, a menudo requieren el cálculo de máximos comunes divisores (MCD) o la verificación de condiciones complejas que involucran polinomios ciclotómicos $\Phi_p$. El autor busca un método que simplifique estos requisitos, apuntando específicamente a una prueba que dependa de una única exponenciación modular sin cálculos de MCD, y que extienda estos conceptos para definir y analizar nuevas familias de primos análogas a los Primos Seguros y los Primos de Sophie Germain.

Metodología
El artículo emplea lemas de teoría de números referentes al orden de los elementos módulo $N$ y las propiedades de divisibilidad de enteros de la forma $Ap+1$.

1. Generalización del Teorema de Proth: El autor demuestra lemas relativos a la divisibilidad de $Ap+1$ por $Dp+1$ y la relación entre el orden de un elemento módulo $N$ y sus factores primos. Estos se utilizan para derivar nuevos criterios de primalidad.
2. Análisis Probabilístico y Heurístico: Para la distribución de las nuevas familias de primos definidas, el artículo utiliza la Conjetura B de Hardy y Littlewood y estimaciones integrales para modelar la densidad de estos primos. Compara estimaciones asintóticas teóricas frente a recuentos empíricos de primos en intervalos específicos.
3. Verificación Computacional: El autor realiza computaciones extensas en primos con longitudes de dígitos variables (desde números pequeños hasta 10,000 dígitos) para probar la precisión de las estimaciones de distribución propuestas.

Contribuciones Clave y Resultados

• Pruebas de Primalidad Simplificadas para $Kp^n + 1$:

  • Teorema 2.3: Proporciona una prueba de primalidad para $N = Kp^n + 1$ (donde $p^n \ge K$) que requiere solo dos condiciones: (i) $a^{Kp^n-1} \equiv L \not\equiv 1 \pmod N$ y (ii) $L^p \equiv 1 \pmod N$. Esto elimina la necesidad del cálculo del MCD requerido en generalizaciones previas (p. ej., Grau et al., 2015).
  • Teorema 2.5: Una generalización adicional que permite un parámetro $j$ ($0 \le j \le n-1$), lo que aumenta el número de bases $a$ válidas que pueden probar la primalidad.
  • Teoremas 3.1 y 3.4: Estos teoremas proporcionan pruebas adicionales para rangos específicos de $j$ y $n$ (p. ej., $p^j \ge p^{n-j} \ge (N-1)^{1/3}$). Estas condiciones permiten valores más grandes de $j$, aumentando así la probabilidad de que una base $a$ elegida al azar satisfaga las condiciones de primalidad, haciendo que la prueba de primalidad tenga más probabilidades de tener éxito.
  • Corolarios: El artículo identifica familias específicas de enteros infinitos (p. ej., $N = 2Kp^2 + 1$ y $N = 2Kp^3 + 1$) donde la primalidad puede certificarse únicamente verificando la condición de Fermat $a^{N-1} \equiv 1 \pmod N$, siempre que se cumplan ciertos límites sobre $K$ y $p$.

• Generalización de Primos Seguros y Primos de Sophie Germain:

  • Definición 4.1 ($a$-SafePrimes): Un primo $N = 2Kp + 1$ se define como un $a$-SafePrime si $2K < \log_a(2Kp+1)$. Esto asegura que el factor primo $p$ de $N-1$ sea significativamente mayor que cualquier otro factor, reflejando la propiedad de los Primos Seguros clásicos.
  • Definición de $a$-SophieGermainPrimes ($a$-SGP): Un primo $p$ es un $a$-SGP si existe al menos un $K$ que satisface $2K < \log_a(2Kp+1)$ tal que $2Kp+1$ también es primo.
  • Análisis de Distribución: El artículo deriva fórmulas asintóticas ($\alpha_1, \alpha_2$) para el recuento de $a$-SafePrimes y estimaciones ($\alpha_3, \alpha_4, \alpha_5$) para la probabilidad de que un dado primo sea un $a$-SGP.
  • Conjeturas sobre la Distribución: Basándose en computaciones que involucran primos de hasta 10,000 dígitos, el autor propone:
    • Conjetura 5.1: La probabilidad de que un dado primo $p$ sea un 2-SophieGermainPrime converge aproximadamente a 0.76 cuando $p \to \infty$.
    • Conjetura 5.2: Una generalización de la anterior para $a$-SGPs, sugiriendo que la probabilidad converge a un límite dependiente de $a$.

• Hallazgos Empíricos:

  • El artículo presenta tablas que comparan los recuentos reales de 2-SafePrimes y 2-SophieGermainPrimes contra las estimaciones asintóticas propuestas. Los resultados muestran una alta precisión incluso para números muy grandes (100 a 10,000 dígitos).
  • El autor aplicó estos hallazgos a los primos de Mersenne, identificando 21 de los primeros 30 primos de Mersenne que también son 2-SophieGermainPrimes, validando la utilidad de las estimaciones para la búsqueda de primos grandes.
  • La probabilidad de que el mayor primo conocido ($2^{82,589,933}-1$) sea un 2-SophieGermainPrime se estima aproximadamente en 0.7637.

Significado
El artículo afirma proporcionar una alternativa computacionalmente más simple a las pruebas de primalidad existentes para la familia $Kp^n + 1$, específicamente al eliminar el paso del MCD manteniendo el rigor. Además, introduce un marco generalizado para los primos Seguros y de Sophie Germain, ofreciendo un modelo estadístico para su distribución que parece robusto incluso para enteros extremadamente grandes. El autor sugiere que estos resultados son útiles para generar primos grandes con fines criptográficos y para comprender la distribución de primos con propiedades estructurales específicas. El trabajo se apoya en la teoría de números establecida (Proth, Pocklington, Hardy-Lemaire) y la extiende a través de nuevos lemas y validación empírica.