Tecnologia

Caccia ai numeri primi con un algoritmo di 2.000 anni fa

Un algoritmo vecchio di 2.300 (circa) anni potrebbe tornare in auge e aiutarci a trovare nuovi numeri primi. Si tratta del Crivello di Eratostene, un metodo funzionale ma troppo impegnativo per i computer moderni. Il matematico Harald Helfgott sostiene però di aver trovato il sistema per tagliare drasticamente le risorse necessarie per eseguirlo.

Il Crivello è un sistema abbastanza semplice da capire anche per chi non ha una laurea in matematica. Si scrivono tutti i numeri in un certo intervallo a partire da 2, diciamo 2-100, e poi si cominciano a eliminarne alcuni secondo un determinato criterio: prima i multipli di 2 (ovviamente i numeri pari non possono essere primi). Poi i multipli di 3, di 5 e così via. Alla fine i numeri rimasti saranno i numeri primi in quel determinato intervallo.

È relativamente semplice anche tradurre il Crivello in un programma per computer, ma non è questo il punto. Con numeri primi sempre più grandi le risorse necessarie per eseguire il programma diventano altrettanto mostruose. Al momento, il numero primo più grande conosciuto è composto da oltre 22 milioni di cifre. La tabella necessaria per trovare quello successivo dovrebbe essere grandicella, abbastanza da mettere in croce qualsiasi PC – tant'è che esiste un popolare benchmark per overclocker, Prime95, che simula la ricerca di numeri primi per stressare al massimo il computer.  

Ed è qui che entra in gioco Harald Helfgott, matematico nato in Perù che già nel 2013 fece parlare di sé per aver dimostrato la congettura debole di Goldbach. Oggi il 38enne ritiene di aver trovato il modo di eseguire il Crivello di Eratostene – il cui autore fu anche direttore della Biblioteca di Alessandria e calcolò la circonferenza della Terra – senza dover fornire il computer di troppa memoria.

F5B2C44A EC2D 43E8 ABC1A413587F68E3
Harald Helfgott

Secondo quanto si legge su Scientific American Alert, Helfgott ha applicato il metodo del cerchio riducendo la memoria necessaria – questo parametro rende infatti il Crivello un metodo poco o per nulla efficiente per un computer.

"Helfgott è riuscito a modificare il Crivello di Eratostene", scrive Matías Loewy, "per farlo funzionare con meno spazio di memoria. In termini matematici, invece di richiedere spazio N, è ora sufficiente avere la radice cubica di N". "Per calcolare tutti i primi fino a un trilione (un miliardo di miliardi), la versione modificata del Crivello ha bisogno solo di qualche milione di bit invece di un miliardo", aggiunge lo stesso Helfgott.

"Immaginiamo di essere un computer", spiega Jean Carlos Cortissoz Iriarte (Cornell University e Universidad de Los Andes), "e che per salvare dati in memoria si usino fogli di carta. Per calcolare i numeri primi tra 1 e 1.000.000 ti servono 200 risme di carta (10.000 fogli – sic), ma con l'algoritmo proposto da Helfgott te ne basterà un quinto di una risma (circa 100 fogli)".

Ciliegina sulla torta, secondo Helfgott questa nuova versione del Crivello non è interessante solo per la ricerca di nuovi numeri primi – attività che di per sé sarebbe già del tutto affascinante – ma si presta bene anche per la fattorizzazione. Quest'ultima è alla base della moderna crittografia.