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

Sintesi Tecnica: Un Test di Primalità per Numeri della forma $Kp^n + 1$ e una Generalizzazione di Primi Sicuri e Primi di Sophie Germain

Enunciato del Problema
Il documento affronta la sfida computazionale di determinare la primalità di interi della forma $N = Kp^n + 1$, dove $p$ è un numero primo e $K < p^n$. Sebbene il test di primalità di Fermat ($a^{N-1} \equiv 1 \pmod N$) sia computazionalmente economico, esso è probabilistico e insufficiente per certificare la primalità da solo. I metodi deterministici esistenti, come il teorema di Proth (per $N=K2^n+1$) e il teorema di Pocklington, richiedono spesso il calcolo di massimi comuni divisori (MCD) o la verifica di condizioni complesse riguardanti i polinomi ciclotomici $\Phi_p$. L'autore mira a un metodo che semplifichi tali requisiti, puntando specificamente a un test che si basi su un'unica esponenziazione modulare senza calcoli di MCD, e che estenda questi concetti per definire e analizzare nuove famiglie di primi analoghe ai Primi Sicuri e ai Primi di Sophie Germain.

Metodologia
Il documento impiega lemmi di teoria dei numeri riguardanti l'ordine degli elementi modulo $N$ e le proprietà di divisibilità degli interi della forma $Ap+1$.

1. Generalizzazione del Teorema di Proth: L'autore dimostra lemmi riguardanti la divisibilità di $Ap+1$ per $Dp+1$ e la relazione tra l'ordine di un elemento modulo $N$ e i suoi fattori primi. Questi vengono utilizzati per derivare nuovi criteri di primalità.
2. Analisi Probabilistica ed Euristica: Per la distribuzione delle nuove famiglie di primi definite, il documento utilizza la Congettura B di Hardy e Littlewood e stime integrali per modellare la densità di questi primi. L'autore confronta le stime asintotiche teoriche con i conteggi empirici di primi in intervalli specifici.
3. Verifica Computazionale: L'autore esegrone estese computazioni su primi con lunghezze di cifre variabili (da numeri piccoli fino a 10.000 cifre) per testare l'accuratezza delle stime di distribuzione proposte.

Contributi Chiave e Risultati

• Test di Primalità Semplificati per $Kp^n + 1$:

  • Teorema 2.3: Fornisce un test di primalità per $N = Kp^n + 1$ (dove $p^n \ge K$) che richiede solo due condizioni: (i) $a^{Kp^n-1} \equiv L \not\equiv 1 \pmod N$ e (ii) $L^p \equiv 1 \pmod N$. Ciò elimina la necessità del calcolo del MCD richiesto dalle precedenti generalizzazioni (ad es., Grau et al., 2015).
  • Teorema 2.5: Una ulteriore generalizzazione che permette un parametro $j$ ($0 \le j \le n-1$), aumentando il numero di basi $a$ valide che possono provare la primalità.
  • Teoremi 3.1 e 3.4: Questi teoremi forniscono ulteriori test per specifici intervalli di $j$ e $n$ (ad es., $p^j \ge p^{n-j} \ge (N-1)^{1/3}$). Queste condizioni permettono valori più grandi di $j$, aumentando così la probabilità che una base $a$ scelta casualmente soddisfi le condizioni di primalità, rendendo la prova di primalità più probabile.
  • Corollari: Il documento identifica specifiche famiglie infinite di interi (ad es., $N = 2Kp^2 + 1$ e $N = 2Kp^3 + 1$) dove la primalità può essere certificata verificando esclusivamente la condizione di Fermat $a^{N-1} \equiv 1 \pmod N$, a patto che siano soddisfatti specifici limiti su $K$ e $p$.

• Generalizzazione di Primi Sicuri e Primi di Sophie Germain:

  • Definizione 4.1 ($a$-SafePrimes): Un numero primo $N = 2Kp + 1$ è definito come un $a$-SafePrime se $2K < \log_a(2Kp+1)$. Ciò assicura che il fattore primo $p$ di $N-1$ sia significativamente più grande di qualsiasi altro fattore, rispecchiando la proprietà dei classici Primi Sicuri.
  • Definizione di $a$-SophieGermainPrimes ($a$-SGP): Un numero primo $p$ è un $a$-SGP se esiste almeno un $K$ che soddisfa $2K < \log_a(2Kp+1)$ tale che $2Kp+1$ sia anch'esso primo.
  • Analisi della Distribuzione: Il documento deriva formule asintotiche ($\alpha_1, \alpha_2$) per il conteggio degli $a$-SafePrimes e stime ($\alpha_3, \alpha_4, \alpha_5$) per la probabilità che un dato primo sia un $a$-SGP.
  • Congetture sulla Distribuzione: Basandosi su computazioni riguardanti primi fino a 10.000 cifre, l'autore propone:
    • Congettura 5.1: La probabilità che un dato primo $p$ sia un 2-SophieGermainPrime converge approssimativamente a 0,76 quando $p \to \infty$.
    • Congettura 5.2: Una generalizzazione della precedente per gli $a$-SGPs, suggerendo che la probabilità converga a un limite dipendente da $a$.

• Risultati Empirici:

  • Il documento presenta tabelle che confrontano i conteggi effettivi di 2-SafePrimes e 2-SophieGermainPrimes rispetto alle proposte stime asintotiche. I risultati mostrano un'alta accuratezza anche per numeri molto grandi (da 100 a 10.000 cifre).
  • L'autore ha applicato queste scoperte ai primi di Mersenne, identificando 21 dei primi 30 primi di Mersenne che sono anche 2-SophieGermainPrimes, convalidando l'utilità delle stime per la ricerca di grandi numeri primi.
  • La probabilità che il più grande primo noto ($2^{82.589.933}-1$) sia un 2-SophieGermainPrime è stimata approssimativamente come 0,7637.

Significatività
Il documento sostiene di fornire un'alternativa computazionalmente più semplice agli esistenti test di primalità per la famiglia $Kp^n + 1$, specificamente rimuovendo il passaggio del MCD pur mantenendo il rigore. Inoltre, introduce un quadro generalizzato per i primi Sicuri e di Sophie Germain, offrendo un modello statistico per la loro distribuzione che appare robusto anche per interi estremamente grandi. L'autore suggerisce che questi risultati siano utili per generare grandi numeri primi a scopi crittografici e per comprendere la distribuzione dei numeri primi con specifiche proprietà strutturali. Il lavoro si basa sulla teoria dei numeri consolidata (Proth, Pocklington, Hardy-Littlewood) ed estende queste attraverso nuovi lemmi e validazione empirica.