Don't take life too seriously: it's just a temporary situation

Primi sicuri

Teoria dei numeri 

Se p è un primo di Sophie Germain, q = 2p + 1 è un primo sicuro.

Il termine deriva dal fatto che q – 1 ha un fattore molto grande mentre alcuni algoritmi di scomposizione in fattori primi impiegano molto meno tempo a trovare un fattore primo p di un intero, se p – 1 è il prodotto di fattori primi piccoli. Il prodotto di due primi sicuri rappresenta quindi un caso particolarmente sfavorevole per questi algoritmi. Questo rende i primi sicuri particolarmente utili nella crittografia a chiave pubblica, sia utilizzando l’algoritmo RSA, sia utilizzando algoritmi basati sul logaritmo discreto, come quello di Diffie – Hellmann.

La ricerca dei primi sicuri è molto più veloce di quella dei primi forti (II), nonostante questi ultimi siano molto più frequenti; il motivo è che dato un primo p, non serve scomporre p – 1, ma basta verificare se 2p + 1 è primo e in questo caso si può usare il test di Pocklington (v. numeri primi), particolarmente efficiente.

 

Nessun primo di Fermat è sicuro, tranne 5.

Nessun primo di Mersenne è sicuro, tranne 7.

 

Tranne 5 e 7, i primi sicuri sono tutti della forma 12k – 1.

 

I primi sicuri minori di 1000 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.

Naturalmente i numeri primi usati nelle applicazioni crittografiche serie sono enormi, di centinaia o addirittura migliaia di cifre.

 

Per i massimi primi sicuri noti v. primi di Sophie Germain.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.