4. Quanti sono
i numeri primi?

 

 

In questo paragrafo ci chiediamo quanti sono i numeri primi: a parte il Teorema di Euclide 4.1 e la sua dimostrazione, talmente belli che non riusciamo a resistere alla tentazione di includerli, vogliamo anche fare un discorso di “densità” dei primi nella successione dei numeri naturali. In altre parole, vi sono molte successioni interessanti di interi, come i quadrati perfetti, le potenze di 2, i numeri di Fibonacci, e molte altre, e tutte queste, per la loro stessa definizione, hanno infiniti termini, ma se andiamo a contare il numero dei loro termini nell'intervallo [1,N] , con N grande, troviamo risultati piuttosto diversi. Alla luce del Teorema di Euclide, ha senso porsi questa domanda anche per la successione dei numeri primi.

Teorema 4.1 (Euclide) Esistono infiniti numeri primi.

Come accennavamo precedentemente, la dimostrazione del Teorema di Euclide è considerata una delle “gemme” della matematica antica; per tale ragione la riportiamo in questa sede.

Supponiamo dunque per assurdo che esista solamente un numero finito di primi e che questi siano esattamente p1<p2<···<pk . Allora il numero

N=p1p2···pk + 1

non può essere anch'esso primo (perché non è presente nell'elenco precedente); d'altronde, siccome N non è divisibile per alcun pi, i=1, . . . ,k, deve anch'esso essere primo. Il che è chiaramente una contraddizione. Dunque l'insieme dei numeri primi non può essere finito e quindi il Teorema di Euclide è dimostrato.

Whitfield Diffie e Martin Hellman

Dopo aver dimostrato che esistono infiniti numeri primi è importante capire quale sia la loro densità negli interi. Il saper rispondere a questo problema non solo è significativo da un punto di vista teorico, ma ha anche riflessi applicativi poiché alcuni tra i più usati metodi crittografici moderni si basano sulla “facilità” di costruire numeri primi e sulla “difficoltà” di determinare la fattorizzazione di interi. Se i primi fossero “pochi” sarebbero difficili da costruire e di conseguenza il determinare la fattorizzazione di un intero dato risulterebbe facile.

Il primo passo nel capire quale fosse la densità dei primi fu fatto alla fine del XVIII secolo da Gauss il quale congetturò che il numero dei primi fino ad N , N molto “grande”, fosse

dove

π(N)=numero dei primi fino a N

e la notazione F(N)∼G(N) indica che il rapporto F(N)/G(N) ha limite 1 quando N tende a +∞. Il fatto sorprendente è che Gauss elaborò la propria congettura basandosi solamente sulle (scarne) informazioni fornite dalle tavole dei numeri primi disponibili all'epoca.
La congettura di Gauss fu dimostrata indipendentemente nel 1896 da Hadamard e de la Vallée Poussin (e dopo allora assunse il nome di Teorema dei Numeri Primi) usando l'idea fondamentale introdotta da Riemann nel 1858: studiare la distribuzione dei primi mediante l'analisi complessa.
Non ci soffermiamo sulle idee di Riemann e sul ruolo fondamentale che la sua funzione ζ ha avuto nello sviluppo della Teoria dei Numeri perché questo discorso ci porterebbe troppo lontano. Notiamo solamente che, da un punto di vista euristico, il Teorema dei Numeri Primi consente di aspettarci che, per N abbastanza grande, esista un primo ogni log N interi circa, ossia che esistano “tanti” numeri primi.
Facciamo anche notare che la densità dei primi fino ad N è nettamente maggiore rispetto a quelle delle successioni menzionate nella prima parte di questo paragrafo; infatti nell'intervallo [1,N] ci sono approssimativamente √N quadrati perfetti, circa log2N potenze di 2 ed approssimativamente logΦN numeri di Fibonacci, dove Φ=(1+√5)/2 è il numero aureo.
Le definizioni e proprietà discusse qui sopra danno origine ad una certa quantità di interessanti problemi teorici e pratici, che discuteremo nel resto di questo articolo e in quelli che lo seguiranno: ne diamo una breve descrizione complessiva, prima di passare alla trattazione dettagliata.

Come generare numeri primi. In molte applicazioni, soprattutto di tipo crittografico, è necessario determinare numeri primi “grandi,” con un numero di cifre decimali dell'ordine di 100 o più: vedremo che un metodo di calcolo che proviene dall'antichità classica, il Crivello di Eratostene, è ancora essenzialmente il modo migliore per determinare tutti i numeri primi in un intervallo di interi consecutivi, ed è di valido ausilio nella ricerca di numeri primi grandi privi di forma particolare.

Come riconoscere i numeri primi. Dato un intero “grande” ci si può chiedere se questo sia primo o meno; non è necessario verificare esplicitamente la definizione, come vedremo, ma è possibile rispondere a questa domanda in modo piuttosto efficiente usando importanti risultati teorici che permettono di “riconoscere” i numeri primi fra tutti gli interi.

Come scomporre in fattori primi. In alcune situazioni non ci si può accontentare della semplice conoscenza del fatto che un certo intero non è primo, ma è necessario conoscerne esplicitamente tutti i fattori primi. Viceversa, dato che alcuni sistemi crittografici importanti (per esempio, RSA) si basano sulla presunta difficoltà di determinare i fattori primi di interi composti grandi scelti in modo opportuno, è interessante conoscere i limiti degli attuali algoritmi di fattorizzazione, per poter scegliere i parametri dei crittosistemi avendo un buon margine di sicurezza.

Come convincere della primalità di un intero. Si tratta di un curioso problema pratico: supponiamo di aver dimostrato in qualche modo che un certo intero è effettivamente un numero primo. È possibile convincere un'altra persona della correttezza della dimostrazione senza doverla replicare interamente?
In altre parole, esiste un “certificato” che garantisca la primalità? Non è un problema ozioso, in quanto gli utenti dei crittosistemi moderni hanno bisogno di uno o più numeri primi, e spesso non hanno i mezzi teorici e pratici per generarli (cioè per generarne di grandezza adeguata all'applicazione crittografica che hanno in mente), e quindi sono costretti ad “acquistarli” da qualcuno. Per questo è stato introdotto il concetto di “certificato succinto” che garantisca l'acquirente, senza che questi abbia la necessità di ripetere integralmente il calcolo eseguito dal venditore.