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

Technische Samenvatting: Een Primaaltest voor $Kp^n + 1$ Getallen en een Generalisatie van Veilige Primen en Sophie Germain-Primen

Probleemstelling
Het artikel behandelt de computationele uitdaging van het bepalen van de primordialiteit van gehele getallen van de vorm $N = Kp^n + 1$, waarbij $p$ een priemgetal is en $K < p^n$. Hoewel de Fermat-primaaltest ($a^{N-1} \equiv 1 \pmod N$) computationeel goedkoop is, is deze probabilistisch en onvoldoende om primordialiteit op zichzelf te certificeren. Bestaande deterministische methoden, zoals de Proth-stelling (voor $N=K2^n+1$) en de Pocklington-stelling, vereisen vaak het berekenen van grootste gemeenschappelijke delers (GCD's) of het verifiëren van complexe condities met betrekking tot cyclotomische polynomen $\Phi_p$. De auteur streeft naar een methode die deze vereisten vereenvoudigt, specifiek gericht op een test die berust op een enkele modulaire exponentiatie zonder GCD-berekeningen, en breidt deze concepten uit om nieuwe families van priemgetallen te definiëren en te analyseren die analoog zijn aan Veilige Primen en Sophie Germain-Primen.

Methodologie
Het artikel maakt gebruik van getaltheoretische lemma's betreffende de orde van elementen modulo $N$ en de deelbaarheidseigenschappen van gehele getallen van de vorm $Ap+1$.

1. Generalisatie van de Proth-stelling: De auteur bewijst lemma's over de deelbaarheid van $Ap+1$ door $Dp+1$ en de relatie tussen de orde van een element modulo $N$ en de priemfactoren ervan. Deze worden gebruikt om nieuwe primordialiteitscriteria af te leiden.
2. Probabilistische en Heuristische Analyse: Voor de distributie van de nieuw gedefinieerde priemgetalfamilies gebruikt het artikel de Hardy-Littlewood Conjectuur B en integraal schattingen om de dichtheid van deze priemgetallen te modelleren. Het vergelijkt theoretische asymptotische schattingen met empirische tellingen van priemgetallen in specifieke intervallen.
3. Computationele Verificatie: De auteur voert uitgebreide berekeningen uit op priemgetallen met variërende aantal cijfers (van kleine getallen tot 10.000 cijfers) om de nauwkeurigheid van de voorgestelde distributieschattingen te testen.

Belangrijkste Bijdragen en Resultaten

• Vereenvoudigde Primaaltests voor $Kp^n + 1$:

  • Stelling 2.3: Biedt een primordialiteitstest voor $N = Kp^n + 1$ (waarbij $p^n \ge K$) die slechts twee condities vereist: (i) $a^{Kp^n-1} \equiv L \not\equiv 1 \pmod N$ en (ii) $L^p \equiv 1 \pmod N$. Dit elimineert de noodzaak voor de GCD-berekening die vereist is in eerdere generalisaties (bijv. Grau et al., 2015).
  • Stelling 2.5: Een verdere generalisatie die een parameter $j$ toestaat ($0 \le j \le n-1$), wat het aantal geldige bases $a$ vergroot die primordialiteit kunnen bewijzen.
  • Stellingen 3.1 en 3.4: Deze stellingen bieden aanvullende tests voor specifieke bereiken van $j$ en $n$ (bijv. $p^j \ge p^{n-j} \ge (N-1)^{1/3}$). Deze condities staan grotere waarden van $j$ toe, waardoor de kans dat een willekeurig gekozen basis $a$ aan de primordialiteitscondities voldoet wordt vergroot, wat de kans dat het bewijs van primordialiteit slaagt, groter maakt.
  • Corollaria: Het artikel identificeert specifieke oneindige families van gehele getallen (bijv. $N = 2Kp^2 + 1$ en $N = 2Kp^3 + 1$) waar primordialiteit gecertificeerd kan worden door enkel de Fermat-conditie $a^{N-1} \equiv 1 \pmod N$ te verifiëren, mits specifieke grenzen aan $K$ en $p$ worden voldaan.

• Generalisatie van Veilige Primen en Sophie Germain-Primen:

  • Definitie 4.1 ($a$-VeiligePrimen): Een priemgetal $N = 2Kp + 1$ wordt gedefinieerd als een $a$-VeiligePrime als $2K < \log_a(2Kp+1)$. Dit zorgt ervoor dat de priemfactor $p$ van $N-1$ aanzienlijk groter is dan elke andere factor, wat de eigenschap van klassieke Veilige Primen weerspiegelt.
  • Definitie van $a$-SophieGermainPrimes ($a$-SGP): Een priemgetal $p$ is een $a$-SGP als er ten minste één $K$ bestaat die voldoet aan $2K < \log_a(2Kp+1)$ zodanig dat $2Kp+1$ ook een priemgetal is.
  • Distributieanalyse: Het artikel leidt asymptotische formules ($\alpha_1, \alpha_2$) af voor de telling van $a$-VeiligePrimes en schattingen ($\alpha_3, \alpha_4, \alpha_5$) voor de waarschijnlijkheid dat een gegeven priemgetal een $a$-SGP is.
  • Conjecturen over Distributie: Gebaseerd op berekeningen met priemgetallen tot 10.000 cijfers, stelt de auteur voor:
    • Conjectuur 5.1: De waarschijnlijkheid dat een gegeven priemgetal $p$ een 2-SophieGermainPrime is, convergeert naar ongeveer 0,76 wanneer $p \to \infty$.
    • Conjectuur 5.2: Een generalisatie hiervan voor $a$-SGPs, die suggereert dat de waarschijnlijkheid convergeert naar een limiet die afhankelijk is van $a$.

• Empirische Bevindingen:

  • Het artikel presenteert tabellen die de werkelijke tellingen van 2-VeiligePrimes en 2-SophieGermainPrimes vergelijken met de voorgestelde asymptotische schattingen. De resultaten tonen een hoge nauwkeurigheid, zelfs voor zeer grote getallen (100 tot 10.000 cijfers).
  • De auteur heeft deze bevindingen toegepast op Mersenne-priemgetallen, waarbij 21 van de eerste 30 Mersenne-priemgetallen werden geïdentificeerd als 2-SophieGermainPrimes, wat de bruikbaarheid van de schattingen voor het zoeken naar grote priemgetallen valideert.
  • De waarschijnlijkheid dat het grootste bekende priemgetal ($2^{82.589.933}-1$) een 2-SophieGermainPrime is, wordt geschat op ongeveer 0,7637.

Betekenis
Het artikel beweert een computationeel eenvoudiger alternatief te bieden voor bestaande primordialiteitstests voor de $Kp^n + 1$ familie, specifiek door de GCD-stap te verwijderen terwijl de striktheid behouden blijft. Bovendien introduceert het een gegeneraliseerd kader voor Veilige en Sophie Germain-primen, en biedt het een statistisch model voor hun distributie dat zelfs voor extreem grote gehele getallen robuust lijkt. De auteur suggereert dat deze resultaten nuttig zijn voor het genereren van grote priemgetallen voor cryptografische doeleinden en voor het begrijpen van de distributie van priemgetallen met specifieke structurele eigenschappen. Het werk steunt op gevestigde getaltheorie (Proth, Pocklington, Hardy-Littlewood) en breidt deze uit via nieuwe lemma's en empirische validatie.