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

Résumé Technique : Un test de primalité pour les nombres de la forme $Kp^n + 1$ et une généralisation des nombres premiers de type « Safe Primes » et « Sophie Germain Primes »

Énoncé du problème
L'article traite du défi computationnel consistant à déterminer la primalité des entiers de la forme $N = Kp^n + 1$, où $p$ est un nombre premier et $K < p^n$. Bien que le test de primalité de Fermat ($a^{N-1} \equiv 1 \pmod N$) soit peu coûteux en termes de calcul, il est probabiliste et insuffisant pour certifier la primalité à lui seul. Les méthodes déterministes existantes, telles que le théorème de Proth (pour $N=K2^n+1$) et le théorème de Pocklington, nécessitent souvent le calcul de plus grands commun diviseurs (PGCD) ou la vérification de conditions complexes impliquant des polynômes cyclotomiques $\Phi_p$. L'auteur cherche une méthode qui simplifie ces exigences, en visant spécifiquement un test reposant sur une seule exponentiation modulaire sans calcul de PGCD, et étend ces concepts pour définir et analyser de nouvelles familles de nombres premiers analogues aux « Safe Primes » et « Sophie Germain Primes ».

Méthodologie
L'article emploie des lemmes de théorie des nombres concernant l'ordre des éléments modulo $N$ et les propriétés de divisibilité des entiers de la forme $Ap+1$.

1. Généralisation du théorème de Proth : L'auteur démontre des lemmes concernant la divisibilité de $Ap+1$ par $Dp+1$ et la relation entre l'ordre d'un élément modulo $N$ et ses facteurs premiers. Ces lemmes sont utilisés pour dériver de nouveaux critères de primalité.
2. Analyse probabiliste et heuristique : Pour la distribution des nouvelles familles de nombres premiers définies, l'article utilise la conjecture B de Hardy et Littlewood ainsi que des estimations intégrales pour modéliser la densité de ces nombres premiers. Il compare les estimations asymptotiques théoriques aux décomptes empiriques de nombres premiers dans des intervalles spécifiques.
3. Vérification computationnelle : L'auteur effectue des calculs approfondis sur des nombres premiers de longueurs de chiffres variables (allant de petits nombres jusqu'à 10 000 chiffres) pour tester l'exactitude des estimations de distribution proposées.

Contributions clés et résultats

• Tests de primalité simplifiés pour $Kp^n + 1$ :

  • Théorème 2.3 : Fournit un test de primalité pour $N = Kp^n + 1$ (où $p^n \ge K$) ne nécessitant que deux conditions : (i) $a^{Kp^n-1} \equiv L \not\equiv 1 \pmod N$ et (ii) $L^p \equiv 1 \pmod N$. Cela élimine le besoin de calcul de PGCD requis par les généralisations précédentes (ex. Grau et al., 2015).
  • Théorème 2.5 : Une généralisation supplémentaire permettant un paramètre $j$ ($0 \le j \le n-1$), ce qui augmente le nombre de bases $a$ valides pouvant prouver la primalité.
  • Théorèmes 3.1 et 3.4 : Ces théorèmes fournissent des tests supplémentaires pour des plages spécifiques de $j$ et $n$ (par exemple, $p^j \ge p^{n-j} \ge (N-1)^{1/3}$). Ces conditions permettent des valeurs plus grandes de $j$, augmentant ainsi la probabilité qu'une base $a$ choisie au hasard satisfasse les conditions de primalité, rendant la preuve de primalité plus susceptible de réussir.
  • Corollaires : L'article identifie des familles infinies spécifiques d'entiers (par exemple, $N = 2Kp^2 + 1$ et $N = 2Kp^3 + 1$) où la primalité peut être certifiée uniquement par la vérification de la condition de Fermat $a^{N-1} \equiv 1 \pmod N$, à condition que des bornes spécifiques sur $K$ et $p$ soient respectées.

• Généralisation des « Safe Primes » et « Sophie Germain Primes » :

  • Définition 4.1 ($a$-SafePrimes) : Un nombre premier $N = 2Kp + 1$ est défini comme un $a$-SafePrime si $2K < \log_a(2Kp+1)$. Cela garantit que le facteur premier $p$ de $N-1$ est significativement plus grand que tout autre facteur, reflétant la propriété des « Safe Primes » classiques.
  • Définition de $a$-SophieGermainPrimes ($a$-SGP) : Un nombre premier $p$ est un $a$-SGP s'il existe au moins un $K$ satisfaisant $2K < \log_a(2Kp+1)$ tel que $2Kp+1$ soit également premier.
  • Analyse de distribution : L'article dérive des formules asymptotiques ($\alpha_1, \alpha_2$) pour le décompte des $a$-SafePrimes et des estimations ($\alpha_3, \alpha_4, \alpha_5$) pour la probabilité qu'un nombre premier donné soit un $a$-SGP.
  • Conjectures sur la distribution : Sur la base de calculs impliquant des nombres premiers allant jusqu'à 10 000 chiffres, l'auteur propose :
    • Conjecture 5.1 : La probabilité qu'un nombre premier $p$ donné soit un 2-SophieGermainPrime converge vers environ 0,76 lorsque $p \to \infty$.
    • Conjecture 5.2 : Une généralisation de la précédente pour les $a$-SGPs, suggérant que la probabilité converge vers une limite dépendant de $a$.

• Résultats empiriques :

  • L'article présente des tableaux comparant les décomptes réels de 2-SafePrimes et de 2-SophieGermainPrimes par rapport aux estimations asymptotiques proposées. Les résultats montrent une grande précision, même pour des nombres extrêmement grands (100 à 10 000 chiffres).
  • L'auteur a appliqué ces résultats aux nombres premiers de Mersenne, identifiant 21 des 30 premiers nombres premiers de Mersenne qui sont également des 2-SophieGermainPrimes, validant l'utilité des estimations pour la recherche de grands nombres premiers.
  • La probabilité que le plus grand nombre premier connu ($2^{82,589,933}-1$) soit un 2-SophieGermainPrime est estimée à environ 0,7637.

Signification
L'article affirme fournir une alternative plus simple sur le plan computationnel aux tests de primalité existants pour la famille $Kp^n + 1$, notamment en supprimant l'étape du PGCD tout en maintenant la rigueur. De plus, il introduit un cadre généralisé pour les nombres « Safe » et « Sophie Germain », offrant un modèle statistique pour leur distribution qui semble robuste, même pour des entiers extrêmement grands. L'auteur suggère que ces résultats sont utiles pour générer de grands nombres premiers à des fins cryptographiques et pour comprendre la distribution de nombres premiers possédant des propriétés structurelles spécifiques. Le travail s'appuie sur la théorie des nombres établie (Proth, Pocklington, Hardy-Lidowelle) et l'étend à travers de nouveaux lemmes et une validation empirique.