Alla caccia dei numeri primi

Lo scorso 26 dicembre Jonathan Pace, un volontario della Great Internet Mersenne Prime Search (GIMPS), ha scoperto il più grande numero primo conosciuto fino ad oggi, chiamato M77232917. Questo numero, composto da 23.249.425 cifre, è un cosiddetto numero primo di Mersenne (il cinquantesimo, per la precisione), ovvero ha la forma 2^p-1, dove p è a sua volta un numero primo. Il nome dato ci indica l’esponente p, vale a dire p=77232917. La GIMPS è un’associazione di appassionati di teoria dei numeri (branca della matematica che si occupa, tra le altre cose, proprio dei numeri primi) che fornisce a chiunque lo desideri un programma informatico per analizzare numeri molto grandi e stabilire se essi siano primi oppure no, attraverso un cosiddetto test di primalità. Il signor Pace ha scoperto M77232917 proprio in questo modo e ha così vinto un premio di 3000 dollari messo in palio dall’associazione. Ricordiamo che si definiscono numeri primi quei numeri naturali (interi e positivi) che sono divisibili solo per 1 e per se stessi (il numero 1 non si considera primo).

I numeri primi sono di fondamentale importanza per garantire la sicurezza delle transazioni bancarie online. Creative Commons DeclanTM
I numeri primi sono di fondamentale importanza per garantire la sicurezza delle transazioni bancarie online. Creative Commons DeclanTM

Vale la pena osservare che non tutti i numeri della forma 2^p-1 sono primi. Ciò è valido in alcuni casi:

  • per p=2 otteniamo 2^2-1=3;

  • per p=3 otteniamo 2^3-1=7;

  • per p=5 otteniamo 2^5-1=31.

Ma, per altri valori di p, si ottengono numeri non primi, infatti:

  • per p=11 otteniamo 2^11-1=2047, che è divisibile per 23.

I numeri primi sono affascinanti e misteriosi perché non si è ancora capito alla perfezione come siano distribuiti. In altre parole, non esiste una formula o un algoritmo capaci di fare previsioni esatte sulla loro distribuzione; esistono solo delle stime approssimative. Quindi, dato un numero primo, nessuno sa dire con certezza quanto dista il successivo. Infatti, considerando la parte iniziale della successione dei numeri primi, si ha: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, …

Si sa per certo, invece, che i numeri primi sono infiniti (la prima dimostrazione di tale fatto risale niente meno che a Euclide, 300 a.C.). Ebbene sì: questi particolari numeri catturano l’interesse dei matematici attraverso i secoli da più di 2000 anni. Molte menti brillanti si sono cimentate con i numeri primi, ottenendo alcuni risultati e proponendo congetture. Tra di esse ricordiamo Gauss, Legendre, Riemann e Fermat. Lo stesso Fermat si sbagliò: congetturò infatti che tutti i numeri della forma 2^2^n-1 fossero primi. Ciò è vero fino a n=4, ma per n=5 Eulero dimostrò che non si ottiene un numero primo.

Creative Commons Andy Maguire
Creative Commons Andy Maguire

Lo studio dei numeri primi può influenzare svariati campi della matematica teorica (come la teoria dei gruppi e degli anelli), ma ha anche applicazioni pratiche. La moderna crittografia a chiave pubblica (RSA), infatti, si basa sulla fattorizzazione (ovvero, sulla ricerca dei divisori) di numeri molto grandi: i numeri primi rivestono quindi un ruolo fondamentale in questo aspetto. RSA, però, non è il solo algoritmo di cifratura a chiave pubblica che dipende dai numeri primi; altri esempi classici sono El Gamal e i sistemi basati su curve ellittiche. La sicurezza di RSA, ad esempio, dipende esclusivamente dalla difficoltà di fattorizzare un numero estremamente grande ottenuto come il prodotto di due numeri primi. La differenza principale tra tale algoritmo di crittografia, che prende il nome dalle iniziali dei cognomi dei suoi inventori (Rivest, Shamir e Adleman, ricercatori del prestigioso MIT), e un algoritmo simmetrico è il fatto che quello che viene cifrato con una chiave possa essere decifrato con un’altra, e viceversa. Questo permette sia applicazioni legate alla firma digitale sia lo scambio sicuro di messaggi. Altri esempi di applicazioni pratiche sono i pagamenti e le transazioni bancarie online (i dati personali e delle carte di credito devono rimanere inaccessibili a un terzo ente che non sia il cliente o il venditore-la banca).  Sebbene siano emersi diversi attacchi, tanto teorici quanto pratici, a RSA, finora è sempre stato possibile rendere nuovamente sicuro l’algoritmo aumentando la dimensione dei numeri primi coinvolti: ciò funziona perché l’operazione di fattorizzazione è estremamente costosa e quindi gli attacchi richiedono nuovamente troppe risorse per essere portati a termine. La necessità di disporre di numeri primi sempre più grandi, per tenere testa all’aumento della potenza di calcolo disponibile, è uno dei motivi per cui questo tipo di ricerca è così importante per la crittografia. Un altro uso piuttosto comune di RSA è all’interno dei protocolli di firma digitale. 

La ricerca dei numeri primi ha assunto quindi importanti risvolti pratici e si avvale delle potenze di calcolo sempre più enormi e sofisticate. Fino alla metà del secolo XX però tale ricerca veniva svolta  a mano. Per dare un’idea di quanto siano importanti i computer nel trovare i numeri primi, basta prendere in considerazione la lista dei 50 numeri primi di Mersenne conosciuti. Solo i primi 12 sono stati scoperti prima dell’avvento delle macchine, mentre i restanti 38 risalgono a non più di 65 anni fa. L’ultimo numero di Mersenne scoperto senza l’ausilio dei computer è 2^127-1 e ha 39 cifre.

In conclusione, non si ha nemmeno il tempo di festeggiare: la caccia al cinquantunesimo numero primo di Mersenne è già iniziata!

Alcuni link di riferimento:

  • https://www.mersenne.org/

  • https://it.wikipedia.org/wiki/Lista_di_numeri_primi

 

Davide Ghilardi ha studiato matematica presso l’Università degli Studi di Milano-Bicocca. Dopo il conseguimento a pieni voti della laurea magistrale, si è trasferito a Barcellona, dove è dottorando in ingegneria computazionale e acustica. Oltre all’attività di ricerca, considera di fondamentale importanza l’insegnamento e la divulgazione della matematica.

Rispondi

%d blogger hanno fatto clic su Mi Piace per questo: