Matematica Discreta II
Lezione del giorno 31 ottobre 2007 Numeri primi e test di primalità
Nell’implementazione del sistema crittografico RSA vi è la necessità di trovare numeri primi abbastanza “grandi”, per aumentare la sicurezza del sistema.
Sappiamo che i numeri primi sono infiniti (Teorema di Euclide), ma nella successione dei numeri naturali essi sono distribuiti in modo irregolare.
Per valutare il numero di primi in un certo intervallo [0,x] della semiretta positiva dell’asse reale, definiamo, per ogni reale x0 :
(x)= numero dei primi x Per esempio (22,3)= {2,3,5,7,11,13,17,19}=8
Non esistono formule algebriche per il calcolo esatto di (x). Per esempio, usando i computers, si è verificato che : (10
14) = 3.204.941.750.802
(i valori massimi attualmente calcolati sono intorno a 10
22).
Nel corso del tempo, i matematici hanno cercato funzioni che “approssimassero” (x). Il risultato più famoso è il:
Teorema di Hadamard-De La Vallé Poussin.
Considerata la funzione f(x)=x/log(x) (definita per x>0, x1) dove log(x) è il logaritmo neperiano, si ha: lim π(x) f(x) 1
x
(il teorema si dimostra con metodi analitici).
Quindi, per x abbastanza grande, il rapporto π(x) f(x) è abbastanza vicino a 1, e in un certo senso f(x)=x/log(x) approssima (x).
Per esempio f(10
14) 3.102.103.442.166, da cui
) f(10
) π(10
14 14