NUMERI PRIMI

Ancora oggi il metodo più veloce per trovare tutti i numeri primi inferiori ad un limite L prefissato è il crivello di Eratostene. Si costruisce un elenco E degli interi compresi tra 2 e L. Si cancellano tutti i multipli di 2 tranne 2. Si prende il primo numero non cancellato, che è 3, e si cancellano tutti i suoi multipli (escluso lui stesso). Si continua così fino alla parte intera della radice quadrata di L. I numeri superstiti sono i numeri primi compresi tra 2 e L. Chi lo desidera può vedere il crivello in azione in questa applet

I numeri primi hanno affascinato l'uomo dai tempi più remti. Un numero primo non è rappresentabile come prodotto di interi che lo precedono: la sua comparsa rappresenta dunque l'apparizione di una novità assoluta.

Il Primo Teorema di Euclide sui numeri primi stabilisce che

Ogni numero intero N si scrive in modo unico (a parte l'ordine) come prodotto di numeri primi.

Dal Secondo Teorema di Euclide sui numeri primi sappiamo che

I numeri primi formano una successione infinita.

E' da notare che la dimostrazione di Euclide della esistenza di infiniti numeri primi è costruttiva, fornisce cioè un metodo che consente, almeno in linea di principio, di trovare un numero primo che sia al di fuori di qualsiasi insieme finito Q di numeri primi assegnato!

La tecnica è la seguente. Se Q = {q₁, q₂, q₃, ..., q_m},
calcolo n = q₁ q₂ q₃ ... q_m + 1.
Evidentemente n è coprimo con tutti i q_j contenuti in Q (cioé non ha fattori in comune con essi). Allora tutti i suoi fattori primi sono primi che non stanno in Q

Supponiamo di conoscere soltanto i numeri primi 2 e 3. Allora Q ={2,3}, n = 2 3 + 1 = 7, che è primo. Aggiungo 7 a Q e ho Q = {2, 3, 7}. Al passo seguente ho n = 2 3 7 + 1 = 43. Anche 43 è primo. Lo aggiungo al bottino: Q = {2, 3, 7, 43}. Proseguo, n = 2 3 7 43 + 1 = 1806 = 13 139. Due nuovi individui! Ora Q = {2, 3, 7, 43, 13, 139}, n = 2 3 7 13 139 + 1 = 3263443 che è primo, etc. etc...

Denotiamo la successione dei primi in ordine ascendente con p₁, p₂, p₃, ..., p_n, ...
Avremo allora p₁ = 2, p₂ = 3, p₃ =5, ...
Per esempio: p₁₀ = 29, p₁₀₀ = 541, p₁₀₀₀ = 7979, p₁₀₀₀₀ = 104709.

Una funzione di importanza fondamentale è p(x)

Poniamo p(x) = numero dei primi minori o uguali a x

Pertanto p(10) = 4 perché ci sono 4 primi (2, 3, 5, 7) minori di 10. Ecco alcuni valori di p(x)

p(100) = 25
p(1000) = 168
p(10000) = 1229
p(100000) = 9592
p(1000000) = 78498
p(10000000) = 664579

Nel 2000 si è arrivati (con algoritmi sofisticati ed una grande rete di computers) a 10²²

p(10²²) = 201467286689315906290

I risultati sopra riportati danno il numero esatto dei primi tra 2 e 10ⁿ, per certi valori di n.

E' possibile conoscere un valore approssimato di p(x)?

Il Teorema dei numeri primi (dimostrato indipendentemente da Hadamard e da de la ValléePoussin nel 1896) afferma che

Questo significa che il limite, per x che tende all'infinito, di p(x)/(x/log(x)) è 1.

Il Teorema dei numeri primi ha, tra le altre, due notevoli conseguenze

1. L'ennesimo primo p_n ha grandezza intorno a n log(n).
   

2. La probabilità che un numero x preso a caso sia primo è circa 1/log(x)
   

Per esempio, la probabilità che un intero casuale di 1000 cifre sia primo è circa
1/log(10¹⁰⁰⁰). Teniamo presente che nel Teorema dei numeri primi il logaritmo è in base e: log(10¹⁰⁰⁰) = 1000 log(10) = 2302,59... Quindi, in media, troveremo un numero primo ogni 2302 interi presi a caso.

E' possibile, dato un intero x casuale, provare velocemente che x è primo? Naturalmente esiste un metodo ovvio (di forza bruta): dividerlo per gli interi che lo precedono. Oppure, cosa assai più intelligente, mettere in moto un crivello di Eratostene. Entrambi però richiederebbe tempi proibitivi di calcolo anche con numeri di modesta lunghezza, persino utilizzando supercomputers. C'è una bella sorpresa:

Esistono metodi efficaci per dimostrare che un intero è probabilmente primo con una probabilità di errore che si può rendere piccola a piacere.

Il più semplice, al tempo stesso velocissimo e potente, è basato sul Piccolo teorema di Fermat.

E' dato l'intero x. Si sceglie un intero a, detto base, coprimo con x.

Se a^x-1 = 1 mod x, si dice che x ha passato il test e lo si dichiara probabilmente primo. Altrimenti diciamo che x non ha passato il test, in quest caso x è certamente composto.

Definiamo pseudoprimo un intero composto che sia stato dichiarato probabilmente primo. Il più piccolo pseudoprimo sulla base 2 è 341 (prodotto di 11 per 31).

La cosa più interessante è che la probabilità che un numero composto passi il test su una base casuale diminuisce fortemente all'aumentare di x. Un intero di 1000 cifre composto ha circa una possibilità su 10¹²³ di passare il test di Fermat su una base a scelta a caso!
Una tavola della probabilità che x composto superi il test di Fermat, in funzione del numero delle cifre di x stesso, si trova qui.

Esistono poi anche metodi molto più efficaci, per i quali la probabilità di errore è ancora più bassa. Il punto di forza di tutti questi metodi è che il tempo che impiegano ad eseguire il test su x è polinomiale, cioè è esprimibile mediante un polinomio nel numero delle cifre di x.

Recentemente (nel 2002) tre ricercatori indiani (Agrawal, Saxena e Cayal) hanno trovato un algoritmo che è al tempo stesso polinomiale e deterministico per dimostrare la primalità di un numero.

Questo è un grande risultato, che ha risolto una congettura rimasta aperta per decenni. Il loro algoritmo però non è ancora utilizzato in pratica, perché è molto più lento dei test probabilistici, i quali, del resto, sono quasi certi per i primi di centinaia di cifre che servono attualmente in crittografia.