Numero primo sicuro

In teoria dei numeri, un numero primo sicuro è un numero primo esprimibile nella forma 2p + 1, dove p è anch'esso numero primo; p è detto numero primo di Sophie Germain.

Alcuni numeri primi sicuri sono: 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907 e 2027.^[1]

Distribuzione

Con l'eccezione del numero 7, tutti i numeri primi sicuri sono nella forma 6n − 1, ovvero sono congrui a 5 modulo 6. Allo stesso modo, con l'eccezione di 5 tutti i primi sicuri sono nella forma 4n − 1, cioè sono congrui a 3 modulo 4, come si può facilmente verificare, considerando che p dev'essere un numero dispari. Dato che il minimo comune multiplo di 6 e 4 è 12, tutti i numeri primi sicuri maggiori di 7 devono pertanto essere esprimibili nella forma 12n − 1, ossia devono essere congruenti a 11 modulo 12.

Il più grande numero primo sicuro attualmente conosciuto è 183 027 × 2^{265 440} − 1, ottenuto insieme al corrispondente primo di Sophie Germain da Tom Wu il 22 marzo 2010 utilizzando i programmi Sgsieve e LLR^[2].

Applicazioni crittografiche

Questi numeri primi sono chiamati "sicuri" per via della loro relazione coi numeri primi forti. Se un numero primo q è forte, q + 1 e q − 1 hanno entrambi dei fattori primi "grandi" rispetto al numero stesso. Il numero naturale precedente al primo sicuro q = 2p + 1 ha ovviamente un fattore primo grande, p, ed è quindi un buon candidato ad essere un primo forte. Diversi algoritmi per la fattorizzazione di un numero n richiedono un tempo correlato alle dimensioni dei fattori primi di q − 1, dove q sono i fattori primi di n. Questo è particolarmente vero per l'algoritmo rho di Pollard.

Sebbene il tempo richiesto dagli algoritmi di fattorizzazione più efficienti, attualmente conosciuti, non dipenda dalle dimensioni dei fattori primi di q − 1, questa proprietà è comunque considerata importante in crittografia: ad esempio, lo standard ANSI X9.31 raccomanda di usare primi forti (e.g. non primi sicuri) per i moduli nella cifratura RSA. Questo è dovuto al fatto, che se assumiamo n=pq ma p-1 e q-1 non sono numeri primi forti, allora esistono diverse tecniche di fattorizzazione, che consentono di fattorizzare n tramite tecniche di Fermat e/o Pollard.

I numeri primi sicuri hanno anche un altro ruolo importante in crittografia, venendo utilizzati nei protocolli basati sui logaritmi discreti come lo scambio di chiavi Diffie-Hellman. Se 2p + 1 è un primo sicuro, il gruppo moltiplicativo di modulo 2p + 1 include un sottogruppo il cui ordine è un numero primo grande. In questo modo il modulo è piccolo rispetto a p, e questa caratteristica rende desiderabili sottogruppi di questo tipo.

Dei primi sicuri, che soddisfino determinate congruenze modulari, possono anche essere usati negli algoritmi per la generazione di numeri pseudocasuali.

Altre proprietà

Non sono disponibili test, per determinare se un numero è un primo sicuro, come invece avviene per i primi di Mersenne e i primi di Fermat. Il test di Pocklington può essere adoperato per determinare se 2p + 1 è primo, una volta accertato che p sia primo. Coll'eccezione di 5, non ci sono primi sicuri che siano anche primi di Fermat. Questo perché un primo di Fermat è un primo nella forma 2ⁿ+1, e la metà di n − 1 è una potenza di due. Tranne il 7, non ci sono nemmeno primi sicuri che siano anche di Mersenne, essendo 2^m−1 ≠ 6k − 1.

Così come tutti i termini, tranne l'ultimo di una catena di Cunningham del primo tipo, sono primi di Sophie Germain, tutti gli elementi tranne il primo sono primi sicuri. L'ultimo termine di una catena di Cunnigham è un primo sicuro che finisce per 7 (esprimibile nella forma 10n + 7). Questo perché 2(10n + 7) + 1=20n + 15, che non è primo essendo sicuramente divisibile per 5.

Se un primo sicuro 2p + 1 è congruo a 7 modulo 8, allora è un divisore del p-esimo numero di Mersenne.