Numero primo sicuro

Da Wikipedia, l'enciclopedia libera.

In teoria dei numeri, un numero primo sicuro è un numero primo esprimibile nella forma 2p + 1, dove p è un altro numero primo. p è invece detto numero primo di Sophie Germain. I primi 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[modifica | modifica sorgente]

Con l'eccezione di 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 × 2265 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[modifica | modifica sorgente]

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 parzialmente 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 (non primi sicuri) per i moduli nella cifratura RSA.

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à[modifica | modifica sorgente]

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ò però essere adoperato per determinare se 2p + 1 è primo, una volta accertato che p è 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 2n+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 2m−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 (esprimibibile 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.

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

Note[modifica | modifica sorgente]

  1. ^ (EN) Sequenza A005385 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  2. ^ (EN) The Prime Database: 183027×2265440−1}}
Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica