Trovare numeri primi grandi

Trovare numeri primi grandi

Dovendo utilizzare in molte applicazioni dei numeri primi abbastanza grandi (o numeri primi grandissimi), come facciamo a trovarli? Inoltre, nonostante l’efficienza degli algoritmi nel testare se un numero sia primo o meno, resta il dubbio che i numeri primi siano “pochi” e quindi difficili da determinare.

In tal proposito ci viene in aiuto un teorema sui numeri primi:

Sia pigreca(n) la funzione di distribuzione dei numeri primi, cioè il numero di numeri primi che precedono il numero n. Allora resta verificato il seguente limite:

Quindi se si cerca un numero primo che abbia 100 cifre, occorre verificare “solo”  ln(10100)=230 numeri consecutivi per avere la certezza di trovarne almeno uno.

Numeri Primi e Fattorizzazione nel contesto della sicurezza informatica

La sicurezza del sistema crittografico RSA si fonda sulla differenza enorme esistente tra due tempi di calcolo. Mentre esistono algoritmi che permettono in pochi secondi di trovare numeri primi di centinaia di cifre, e quindi è facile e veloce costruire la funzione che effettua la codifica, occorrerebbero secoli di calcolo su migliaia di computers ultraveloci per fattorizzare un intero grande. Del resto se il malintenzionato non riesce a trovare i fattori di m, non può neanche trovare il numero segreto d che è l’unico che permette di costruire la funzione di decodifica.

Esempio

N.B.:In questo esempio, i valori scelti per p e q, consentono una migliore comprensione del sistema RSA, ma sono troppo bassi per garantire una effettiva sicurezza.

Immaginiamo che i due numeri primi di Alice siano: p=47 e q=61.

Con e=1183, la chiave pubblica di Alice è data dalla coppia (1183, 2867), di conseguenza la funzione per effettuare la cifratura sarà:

C=P1183(mod 2867)

Calcolando il valore di d otteniamo la chiave privata (7, 2867) e la funzione per decrittare:

P=C7(mod 2867)

 

Precedente Numeri primi e Piccolo Teorema di Fermat Successivo Sicurezza del RSA (Rivest Shamir Adleman)

Lascia un commento

*