Numero primo forte

In matematica, un numero primo forte è un numero primo caratterizzato da proprietà particolari. La teoria dei numeri e la crittografia danno due definizioni differenti di numero primo forte.

Definizione secondo la teoria dei numeri

Nella teoria dei numeri un numero primo forte è definito come un numero primo maggiore della media aritmetica tra il numero primo immediatamente successivo e il numero primo immediatamente precedente. In altri termini, è un numero più prossimo al suo numero primo successivo che al suo precedente.

Algebricamente, dato un numero primo $p_{n}$ , dove $n$ è l'indice del numero nell'insieme ordinato dei numeri primi, il numero primo $p$ si dice forte se soddisfa la condizione:

p_{n}>{\frac {p_{n+1}+p_{n-1}}{2}}

Per esempio: il numero 17 è il settimo numero dell'insieme ordinato di numeri primi. La somma del sesto numero primo (13) e dell'ottavo numero primo (19) ritorna 32, la cui metà è 16. Essendo 17>16, in base alla definizione 17 è un numero primo forte.

La sequenza dei primi numeri primi forti è la seguente:^[1]

11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, 107, 127, 137, 149, 163, 179, 191, 197, 223, 227, 239, 251, 269, 277, 281, 307, 311, 331, 347, 367, 379, 397, 419, 431, 439, 457, 461, 479, 487, 499...

Nel caso dei numeri primi gemelli del tipo (p, p+2), se p>5 allora è sempre un numero primo forte, dato che 3 dovrebbe essere un divisore di p-2, che non può essere un numero primo.

Definizione secondo la crittografia

In crittografia, un numero primo $p$ è detto "forte" se soddisfa le condizioni seguenti:^[2]

$p$ è sufficientemente grande da essere utilizzabile per la crittografia; tipicamente, questo richiede che $p$ sia troppo grande per consentire a un criptoanalista di fattorizzare il prodotto tra $p$ e altri numeri primi forti
I fattori primi di $p-1$ sono grandi, ossia $p={a_{1}}{q_{1}}+1$ per un qualche intero $a_{1}$ e un numero primo grande $q_{1}$
${q_{1}}-1$ possiede fattori primi grandi, ossia ${q_{1}}={a_{2}}{q_{2}}+1$ per un qualche intero $a_{2}$ e un numero primo grande $q_{2}$
I fattori primi di $p+1$ sono grandi, ossia $p={a_{3}}{q_{3}}-1$ per un qualche intero $a_{3}$ e un numero primo grande $q_{3}$

Come anche riportato in [2], nella definizione di numero primo forte, non sempre vengono utilizzate tutte le condizioni, di sopra indicate.

È possibile che un numero primo sia un numero primo forte sia secondo la definizione crittografica che secondo la definizione della teoria dei numeri. A titolo di esempio, 439351292910452432574786963588089477522344331 è un numero primo forte secondo la teoria dei numeri perché supera di 62 la media aritmetica dei due numeri primi adiacenti. Senza l'ausilio di un computer, questo numero è un numero primo forte anche secondo la crittografia perché il suo valore meno uno (439351292910452432574786963588089477522344330) ha come fattore primo grande 1747822896920092227343 (di cui a sua volta il numero inferiore di uno possiede il fattore primo grande 1683837087591611009), mentre il suo valore più uno (439351292910452432574786963588089477522344332) ha come fattore primo grande 864608136454559457049 (di cui a sua volta il numero inferiore di uno possiede il fattore primo grande 105646155480762397). Anche utilizzando algoritmi più sofisticati della fattorizzazione per tentativi, questi numeri sono molto difficili da elaborare a mano. I moderni computer algebrici sono invece in grado di fattorizzare questi numeri quasi istantaneamente. Un numero primo per essere crittograficamente forte deve essere molto più grande rispetto a quelli usati in questo esempio.

Applicazioni dei numeri primi forti in crittografia

Sistemi crittografici basati sulla fattorizzazione

Alcuni teorici suggeriscono che il modulo $n$ usato per il processo di generazione delle chiavi con l'algoritmo RSA andrebbe scelto come prodotto tra due numeri primi forti $p$ e $q$ . Questo renderebbe computazionalmente infattibile la scomposizione in fattori di $n=pq$ con l'algoritmo rho di Pollard. Per questo motivo, lo standard ANSI X9.31 richiede l'utilizzo di numeri primi forti per la generazione delle chiavi RSA di firma digitale. Tuttavia, i numeri primi forti non proteggono dalla scomposizione in fattori se si usano algoritmi più nuovi come la crittografia ellittica di Lenstra e il crivello dei campi di numeri generale. Considerato il costo aggiuntivo per la generazione di numeri primi forti, RSA Security non ne raccomanda l'impiego nella generazione delle chiavi. Argomentazioni simili, ma più tecniche, sono state sviluppate anche negli studi di Rivest e Silverman.^[2]

Sistemi crittografici basati sui logaritmi discreti

Stephen Pohlig e Martin Hellman nel 1978 hanno dimostrato che se tutti i fattori di $p-1$ sono inferiori a $\log _{c}p$ allora il problema di risolvere il logaritmo discreto di modulo $p$ è in classe di complessità P. Pertanto, per i sistemi crittografici basati sui logaritmi discreti, come l'algoritmo DSA, si richiede che $p-1$ possieda almeno un fattore primo grande.

Note

^ (EN) A051634 Strong primes, in The On-line Encyclopedia of Integer Sequences, OEIS.
^ ^a ^b (EN) Ron Rivest e Robert Silverman, Are 'Strong' Primes Needed for RSA?, in Cryptology ePrint Archive: Report 2001/007.

Bibliografia

(EN) Tom M. Apostol, Introduction to Analytic Number Theory, New York, Springer-Verlag, 1976, ISBN 0-387-90163-9.
(EN) E. C. Titchmarsh, The Theory of the Riemann Zeta-Function, a cura di D. R. Heath-Brown, Oxford Science Publications, 1986, ISBN 0-19-853369-1.
(EN) Harold M. Edwards, Riemann's Zeta Function, Courier Dover Publications, 2001, ISBN 0-486-41740-9.
(EN) Albert Edward Ingham, The Distribution of Prime Numbers, New York, Cambridge Mathematical Library, 1932, ISBN 0-521-39789-8.

Voci correlate

Numero primo sicuro

Portale Crittografia

Portale Matematica

[1] (EN) A051634 Strong primes, in The On-line Encyclopedia of Integer Sequences, OEIS.

[rivest-2] (EN) Ron Rivest e Robert Silverman, Are 'Strong' Primes Needed for RSA?, in Cryptology ePrint Archive: Report 2001/007.

[1]

[2]