La moltitudine dei numeri primi

I numeri primi sono uno dei pochi argomenti della matematica pura ad arrivare a volte all’onore della cronaca, anche se solo quando viene battuto un record: un po’ come succede nelle specialità meno appariscenti dell’atletica leggera. L’ultima volta è successo a gennaio, quando Curtis Cooper, della University of Central Missouri, ha annunciato di avere scoperto il numero primo più grande conosciuto: è il numero 274207281 – 1. Ha 22 milioni di cifre, ben 5 milioni in più rispetto al primatista precedente. Per dare un’idea degli ordini di grandezza in gioco, basta pensare che il peso stimato dell’universo, espresso in chili, è un numero di sole 53 cifre.

In realtà, anche indipendentemente dal guinness dei primati e dalla spettacolarità delle cifre astronomiche, i numeri primi sono uno degli argomenti più singolari della matematica: a fronte di una definizione molto semplice (sono i numeri divisibili solo per 1 e per sé stessi, cioè 2, 3, 5, 7, 11, 13, 17, eccetera), hanno grandi ricadute pratiche e pongono ai matematici domande ancora lontane dall’avere una risposta.

In questo video (in inglese), un’intervista a Curtis Cooper, lo scopritore del numero primo da record:

 

Qual è il ruolo dei numeri primi nella matematica?

I numeri primi sono per l’algebra un po’ quello che gli elementi della tavola periodica sono per la chimica: sono le componenti minime alla base di tutto l’edificio. Come una molecola d’acqua è formata da due atomi di idrogeno e uno di ossigeno (e quindi la formula è H2O), così per esempio il numero 12 è il prodotto di 2 ∙ 2 ∙ 3: la relazione con cui si combinano gli elementi è il legame chimico, per i numeri primi è la moltiplicazione. La “formula” del 12 si scrive 22 ∙ 3 e si chiama fattorizzazione. Come la formula chimica, la fattorizzazione è unica: l’unica cosa che può cambiare è l’ordine (è equivalente scrivere 22 ∙ 3 o 3 ∙ 22), ma per convenzione si scrivono i fattori primi in ordine crescente. Questo è uno dei motivi per cui il numero 1 non si può considerare un numero primo: se lo fosse, la fattorizzazione di un numero non sarebbe unica perché si potrebbero aggiungere “uni” a volontà senza cambiare il prodotto, e quindi in numerosi teoremi bisognerebbe specificare “numeri primi diversi da 1”.

C’è però una differenza sostanziale: gli elementi chimici sono relativamente pochi (oggi siamo arrivati a 118; si ritiene che potranno aumentare ancora, ma non molto), mentre i numeri primi sono infiniti – e quindi la gara a trovare numeri primi sempre più grandi non avrà mai fine. Che siano infiniti lo sapevano già i Greci, come si evince dagli Elementi di Euclide, il compendio più organico della matematica antica. In effetti è presumibile che i numeri primi fossero conosciuti già da popoli più antichi, come gli Egiziani e i Mesopotamici, ma i primi studi di cui abbiamo notizia certa risalgono appunto ai Greci.

 

elementi-euclide

Uno dei più antichi frammenti degli Elementi di Euclide, datato 100 d.C (immagine: http://www.math.ubc.ca)

Come si cercano i numeri primi?

Il modo più naturale e “ingenuo” per cercare un numero primo è considerare un numero e verificare se è primo. Il metodo più antico per farlo è il crivello di Eratostene, dal nome del matematico ellenistico che lo ideò nel III secolo a.C. Funziona in modo intuitivo: se per esempio vogliamo sapere tutti i numeri primi minori di 1000, per prima cosa scriviamo tutti i numeri naturali fino a 1000 e poi eliminiamo via via prima i multipli di 2, poi quelli di 3, e così via. Alla fine resteranno solo i numeri primi.

Una versione più efficiente di questo metodo è adottata ancora oggi dai software usati per la ricerca dei numeri primi.

Ma ci sono altri “trucchi”. Il più importante riguarda una particolare categoria di numeri primi, i numeri primi di Mersenne (dal matematico francese Marin Mersenne che li ha studiati nel Seicento): sono i numeri primi della forma 2p – 1 (dove p è a sua volta un numero primo). Non sempre, anche se p è primo, il numero 2p – 1 è primo, però a volte sì. Per esempio, per p = 7, 27 – 1 = 127 è primo, mentre 211 – 1 = 2047 è divisibile per 23 e per 89. L’attenzione dei matematici è dedicata ai numeri primi di questo tipo perché, a fianco del crivello di Eratostene, c’è un altro algoritmo (meno immediato, ma molto efficiente) per verificare se un numero di Mersenne è primo. Quindi oggi per cercare i numeri primi si cercano principalmente quelli di questa categoria: si prende un numero primo p (in ordine progressivo, per non saltarne nessuno), si calcola il numero 2p – 1 e si verifica se è primo.

Nel 1996 è nata la Great Internet Mersenne Prime Search (Gimps): un’iniziativa collettiva che raccoglie migliaia di volontari a caccia di numeri primi di Mersenne, di cui fa parte lo stesso Cooper. È per questo che tutti i più recenti numeri primi record sono numeri di Mersenne (compreso l’ultimo, quello del gennaio 2016).

I programmi usati dalla Gimps e dagli altri cercatori di numeri primi si basano sulla combinazione dei vari metodi: per esempio si usa un setaccio simil-Eratostene per cercare i primi tot possibili divisori di un numero e poi l’altro metodo per i rimanenti. La maggior parte delle volte il computer trova un divisore e quindi scarta il numero candidato. La Gimps ha scoperto per esempio che 276372111 – 1 è divisibile per 15.664.800.701.540.248.373.281, e 217504141 – 1 è divisibile per 426.315.489.966.437.174.530.195.419.710.289.226.952.407.399. A oggi, sono in tutto 49 i numeri primi di Mersenne conosciuti: gli ultimi 15 li ha trovati la Gimps.

marsenne

Distribuzione dei numeri primi di Mersenne trovati da GIMPS (immagine: http://www.mersenne.org/primes/)

Il nuovo primatista è stato individuato da Cooper (al suo quarto record in 11 anni) facendo girare uno di questi programmi su un normale computer per 31 giorni, nel 2015. Il software è fatto in modo che alla fine, se il numero in questione risulta essere primo, viene inviato un messaggio di notifica. Curiosamente, in questo caso il messaggio non è arrivato a causa di un problema tecnico. Così Cooper se n’è accorto per caso, solo 4 mesi dopo. In altre parole il nuovo numero primo è stato scoperto dal computer il 17 settembre 2015, ma dall’uomo solo il 7 gennaio 2016 (è però questa la data che fa fede). Il calcolo è stato poi verificato con altri software, per escludere la possibilità di errori.

Cooper si è aggiudicato un premio di 3000 dollari messo in palio dal Gimps. Ma per i prossimi traguardi c’è una ricompensa molto più alta: per il primo numero primo con oltre 100 milioni di cifre l’Electronic Frontier Foundation di San Francisco ha messo in palio 150.000 dollari (da dividere in parti uguali fra lo scopritore, un’organizzazione di beneficienza di sua scelta e la stessa Gimps). Chi volesse inscriversi alla Gimps e tentare l’impresa può farlo qui.

Se vuoi vedere nel dettaglio come funziona il crivello di Eratostene puoi guardare un video cliccando qui (in inglese).

 

Quali sono i campi di applicazione dei numeri primi?

Il principale campo di applicazione dei numeri primi è di gran lunga la crittografia, cioè la scienza che si occupa dei codici segreti: una tecnica impiegata da sempre in ambito militare, ma oggi più importante che mai nell’era delle password e dei codici del bancomat.

Inviare un messaggio crittato comporta due fasi: la prima è la codifica, cioè la traduzione del messaggio originale nel messaggio in codice, da parte di chi lo invia. La seconda è la decodifica, cioè la ricostruzione del messaggio originale da parte del destinatario. In origine i codici erano abbastanza elementari: per esempio nel sistema usato da Giulio Cesare ogni lettera viene sostituita da quella che la segue di tre posizioni nell’ordine alfabetico: la A diventa D, la B diventa E, eccetera (per le ultime lettere si ricomincia ciclicamente: la U diventa A, la V diventa B e la Z diventa C). Così per esempio la parola “Cesare” diventa “Fhvduh”: decisamente difficile da decifrare per chi non conosce il codice.

Il problema con i codici come questo è che se il nemico scopre la “chiave”, cioè il metodo con cui viene crittato il messaggio, potrà decrittarlo facilmente.

Da allora la crittografia ha fatto passi da gigante; il sistema oggi più diffuso, chiamato RSA dalle iniziali dei tre inventori che l’hanno ideato nel 1976 (Ronald Rivest, Adi Shamir e Leonard Adleman), si basa appunto sui numeri primi. I dettagli sono piuttosto complicati, ma l’idea di base si può riassumere in breve.

Immaginiamo che Giulietta voglia inviare un messaggio segreto a Romeo. La prima mossa – e qui sta il trucco – spetta a Romeo, che deve pensare due numeri primi molto grandi, p e q, e poi li moltiplica: pq = n. A questo punto Romeo rende pubblico a tutti (ebbene sì, a tutti!) il numero n, che sarà la chiave del codice: servirà cioè a crittare il messaggio. Giulietta quindi per prima cosa trasforma il proprio messaggio in un numero x (anche semplicemente sostituendo a ogni lettera il suo posto nell’alfabeto: A = 1, B = 2, eccetera). Poi esegue delle operazioni matematiche usando x e n, e infine invia il risultato a Romeo.

Il trucco sta nel fatto che per la codifica basta conoscere n (e quindi Giulietta può crittare il messaggio) mentre la decodifica è abbastanza facile, anche usando un normale computer, solo se si conoscono i due numeri p e q, mentre se si conosce solo n è difficilissima. Anzi, è praticamente impossibile se i numeri sono abbastanza grandi: il fatto è che, dati p e q, è facile trovare n, mentre dato n non è affatto facile trovare p e q. Ma l’unico a conoscere p e q è Romeo, che quindi potrà decodificare tranquillamente il tenero messaggio di Giulietta. Se invece una spia intercetta il messaggio cifrato, anche conoscendo n, non riuscirà comunque a decodificarlo. Ecco l’importanza dei numeri primi. Se infatti p e q non fossero numeri primi, l’impresa di ritrovarli a partire da n sarebbe più facile. 

In questa intervista (dal minuto 3:00) Tommaso Castellani, autore di Risolvere i problemi difficili fornisce altre informazioni sulla crittografia e sul metodo RSA.

La crittografia è stata un’arma decisiva per la vittoria degli Alleati nella Seconda guerra mondiale, come racconta il film The Imitation Game del regista Morten Tyldum. Per saperne di più, puoi leggere questa recensione della pellicola scritta da Dany Maknouz su Aula di Scienze.

Perché è importante trovare numeri primi sempre più grandi?

I numeri primi usati nella crittografia sono molto grandi (maggiori del peso dell’universo in chili) ma lontani dal record: sono numeri dell’ordine di grandezza di centinaia di cifre. Il fatto è che non serve esagerare: se n ha almeno 300 cifre, anche mettendo insieme cento milioni di personal computer ci vorrebbero più di mille anni per trovare p e q e quindi decodificare il messaggio cifrato. Anche se in futuro dovesse rivelarsi necessario usare numeri primi più grandi, basterebbe passare dalle centinaia di cifre alle migliaia. Dunque la ricerca di numeri primi sempre più grandi non ha effettivamente una ricaduta pratica nell’ambito della crittografia. Questo non vuol dire che non serva a nulla. Da un lato, come tutta la ricerca di base, espande le nostre conoscenze – a costi bassissimi anche se paragonati agli standard non faraonici della ricerca scientifica. Dall’altro, i programmi per verificare se un numero è primo sono un banco di prova per i computer. Sappiamo che i computer non sono infallibili (come può testimoniare Cooper). A volte, data la complessità delle architetture informatiche di oggi, è molto difficile individuare eventuali “bachi”. Ebbene, i programmi come quelli per i numeri primi possono scovarli: il software usato dalla Gimps ha scoperto un baco (fortunatamente non grave) nell’ultima versione del sistema Skylake, che la grande ditta Intel usa per realizzare i propri computer. Più in generale, Sidney Keith, della società Squirrels, che ha contribuito a verificare l’esattezza del nuovo primatista dei numeri primi, ha dichiarato a Forbes: «Le tecnologie che perfezioniamo per confermare che la verifica di un numero primo è esatta, in futuro ci potrà aiutare a stabilire che sono esatti anche i risultati dell’analisi di una eventuale cura per il cancro».

 

Quali sono i problemi aperti?

In nessun altro ambito della matematica ci sono domande così semplici da formulare eppure ancora senza risposta. Per esempio: è vero che ogni numero pari (tranne il 2) può essere scritto come somma di due numeri primi? A prima vista sembrerebbe di sì: per esempio 4 = 2 + 2, 10 = 3 + 7, 48 = 31 + 17. E così via. Si chiama “congettura di Goldbach” perché è stata formulata nel 1742 in uno scambio epistolare fra il matematico tedesco Christian Goldbach e lo svizzero Eulero. L’enunciato è valido per tutti i numeri su cui è stato testato finora, ma non esiste una dimostrazione generale e quindi nessuno sa se a un certo punto si troverà un numero pari per cui non vale.

Fra i numerosi problemi aperti sui numeri primi, il più importante è senza dubbio l’ipotesi di Riemann. È una congettura che non riguarda direttamente i numeri primi bensì una particolare funzione complessa, ma se fosse vera implicherebbe una stima sulla distribuzione dei numeri primi, cioè sulla frequenza con cui capitano nell’insieme dei numeri naturali. Sappiamo infatti che sono infiniti, ma non sappiamo se compaiono secondo un qualche ordine.

La congettura risale al matematico tedesco Bernhard Riemann (1826-1866) ed è considerata da molti il problema matematico più arduo fra tutti quelli ancora irrisolti. È l’unico che compare sia nella lista dei 23 problemi matematici più importanti, stilata dal tedesco David Hilbert nel 1900, sia in quella dei 7 “problemi del millennio” proposta cento anni dopo, nel 2000, dal Clay Mathematics Institute anglo-americano, che ha anche messo in palio un premio di un milione di dollari per ognuno dei sette.

ipotesi di riemann

Il manoscritto dell’ipotesi di Riemann (immagine: http://www.claymath.org/millennium-problems/riemann-hypothesis)

Se qualcuno dimostrerà l’ipotesi di Riemann, avrà trovato anche la migliore dimostrazione di come i numeri primi possono essere molto utili nella vita reale.

Qui puoi scaricare un video (in inglese) per saperne di più sull’ipotesi di Riemann.

Per la lezione

Prosegui la lettura

Commenti

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *