Come costruire un grande numero primo | Rivista Quanta

I numeri primi sono cose complicate. Impariamo a scuola che sono numeri senza fattori diversi da 1 e se stessi, e che i matematici sanno da migliaia di anni che ne esiste un numero infinito. Produrne uno a comando non sembra essere difficile.

Ma è. La costruzione di numeri primi arbitrariamente grandi è notevolmente complicata. Fondamentalmente hai due opzioni computazionali, entrambe con svantaggi. Potresti usare la casualità e trovarne uno indovinando, ma il metodo è incoerente: corri il rischio di generare ogni volta un numero primo diverso. Oppure potresti usare un algoritmo più affidabile e deterministico, ma a un costo computazionale elevato.

A maggio, un team di informatici ha mostrato che potrebbe funzionare anche una sorta di approccio ibrido. Hanno pubblicato un algoritmo che combina efficacemente gli approcci casuali e deterministici per produrre un numero primo di una lunghezza specifica, con un'alta probabilità di fornire lo stesso anche se l'algoritmo viene eseguito molte volte. L'algoritmo collega casualità e complessità in modi interessanti e potrebbe anche essere utile per la crittografia, dove alcuni schemi di codifica si basano sulla costruzione di grandi numeri primi.

"Hanno disposto una sequenza di tentativi, ognuno dei quali cercava di costruire un numero primo di lunghezza diversa, e hanno mostrato che uno dei tentativi funziona", ha detto Roei Tell, un informatico teorico dell'Institute for Advanced Study che non era coinvolto nel lavoro. "È una costruzione che emette un numero primo scelto in modo deterministico, ma ti consente di lanciare monete e fare scelte casuali nel processo."

La sfida di creare una ricetta efficiente per i numeri primi ha radici profonde. "In realtà non sappiamo molto su come sono distribuiti i numeri primi, o sulle lacune nei numeri primi", ha detto Ofer Grossman, che studia gli algoritmi pseudocasuali. E se non sappiamo dove trovarli, non esiste un modo semplice per generare un numero primo da zero.

Nel corso del tempo, i ricercatori hanno sviluppato gli approcci di cui sopra. Il modo più semplice è indovinare. Se vuoi un numero primo con 1,000 cifre, ad esempio, puoi scegliere un numero di 1,000 cifre a caso e poi controllarlo. "Se non è primo, provane un altro, e un altro, e così via finché non ne trovi uno", ha detto Rahul Santhanam, un informatico dell'Università di Oxford e coautore del nuovo articolo. "Poiché ci sono molti numeri primi, questo algoritmo ti darà un numero primo con un'alta probabilità, dopo un numero relativamente piccolo di iterazioni." Ma usare la casualità significa che probabilmente otterrai un numero diverso ogni volta, ha detto. Questo potrebbe essere un problema se hai bisogno di coerenza, se, ad esempio, stai utilizzando un metodo crittografico di sicurezza che dipende dalla disponibilità di numeri primi di grandi dimensioni.

L'altro approccio consiste nell'utilizzare un algoritmo deterministico. Potresti scegliere un punto di partenza e iniziare a testare i numeri, in sequenza, per la primalità. Alla fine sei destinato a trovarne uno e il tuo algoritmo produrrà costantemente il primo che trovi. Ma potrebbe volerci un po': se stai cercando un numero primo con 1,000 cifre, anche un calcolo con 2⁵⁰⁰ passaggi - che richiederebbero molto più tempo dell'età dell'universo - non sono sufficienti per garantire il successo.

Nel 2009, il matematico e medaglia Fields Terence Tao voleva fare di meglio. Ha sfidato i matematici a inventare un algoritmo deterministico per trovare un numero primo di una data dimensione entro un limite di tempo computazionale.

Quel limite di tempo è noto come tempo polinomiale. Un algoritmo risolve un problema in tempo polinomiale se il numero di passaggi necessari non è altro che una funzione polinomiale di n, la dimensione dell'input. (Una funzione polinomiale include termini che hanno variabili elevate a potenze intere positive, come n² o 4n³.) Nel contesto della costruzione di numeri primi, n si riferisce al numero di cifre nel numero primo che desideri. Dal punto di vista computazionale, questo non costa molto: gli informatici descrivono i problemi che possono essere risolti da algoritmi in tempo polinomiale come facili. Un problema difficile, al contrario, richiede tempo esponenziale, il che significa che richiede un numero di passaggi approssimati da una funzione esponenziale (che include termini come 2ⁿ).

Per decenni, i ricercatori hanno studiato la connessione tra casualità e durezza. Il problema della costruzione dei numeri primi era considerato facile se si ammetteva la casualità - e ci si accontentava di ricevere ogni volta un numero diverso - e difficile se si insisteva sul determinismo.

Nessuno è ancora riuscito a raccogliere la sfida di Tao, ma il nuovo lavoro ci va vicino. Si basa in gran parte su un approccio introdotto nel 2011 da Shafi Goldwasser e Eran Gat, scienziati informatici presso il Massachusetts Institute of Technology. Hanno descritto algoritmi "pseudodeterministici": ricette matematiche per problemi di ricerca, come trovare grandi numeri primi, che potrebbero sfruttare i vantaggi della casualità e, con alta probabilità, produrre sempre la stessa risposta ogni volta. Userebbero l'efficienza dei bit casuali nella ricetta, che verrebbe de-randomizzata nel risultato, apparendo deterministica.

Da allora i ricercatori hanno esplorato algoritmi pseudodeterministici. Nel 2017, Santhanam e Igor Oliveira dell'Università di Warwick (che ha anche contribuito al nuovo lavoro) descritta un approccio pseudodeterministico alla costruzione di numeri primi che utilizzava la casualità e sembrava deterministico in modo convincente, ma funzionava in tempo "subesponenziale": più veloce dell'esponenziale, ma più lento del tempo polinomiale. Poi nel 2021, Tell e Liji Chen, un informatico dell'Università della California, Berkeley, esplorato come utilizzare un problema difficile per costruire un generatore di numeri pseudocasuali (un algoritmo che genera una stringa di numeri indistinguibili da un output casuale). "[Abbiamo] trovato una nuova connessione tra durezza e pseudocasualità", ha detto Chen.

I pezzi finalmente si sono riuniti nella primavera del 2023, durante un bootcamp sulla complessità computazionale al Simons Institute for the Theory of Computing di Berkeley, quando i ricercatori iniziarono a lavorare insieme sul problema, intrecciando i risultati del passato. Per il nuovo lavoro, ha detto Chen, Hanlin Ren, scienziato informatico a Oxford e coautore, ha avuto l'idea iniziale di combinare il risultato di Chen-Tell con l'approccio di Santhanam-Oliveira in un modo nuovo. Quindi l'intero team ha sviluppato le idee in modo più completo per produrre il nuovo documento.

L'algoritmo pseudodeterministico risultante, ha affermato Santhanam, ha utilizzato nuovi modi di guardare al lavoro passato per produrre numeri primi in tempo polinomiale. È probabile che abbia utilizzato la casualità per produrre un numero primo di una lunghezza specifica e lo strumento è più accurato dell'ipotesi casuale e più efficiente dal punto di vista computazionale del crunch deterministico.

Il nuovo algoritmo è anche straordinariamente semplice, ha affermato Santhanam, e può essere applicato a un'ampia gamma di problemi di ricerca, in realtà a qualsiasi sottoinsieme denso di numeri, come i numeri primi, per i quali l'appartenenza può essere determinata in tempo polinomiale. Ma non è perfetto. L'algoritmo funziona per infinite lunghezze di input, ma non copre tutte le lunghezze delle cifre. Potrebbero esserci ancora alcuni valori di n là fuori per i quali l'algoritmo non produce deterministicamente un numero primo.

"Sarebbe bello sbarazzarsi di quel piccolo avvertimento", ha detto Grossman.

L'obiettivo finale, ha affermato Santhanam, è trovare un algoritmo che non richieda affatto casualità. Ma quella ricerca rimane aperta. "Il determinismo è ciò che vorremmo usare", ha detto.

Ma ha anche sottolineato che i processi pseudocasuali sono strumenti potenti e progetti come la costruzione di numeri primi sono solo un modo per usarli per collegare idee di matematica, informatica, teoria dell'informazione e altre aree.

"È emozionante cercare di pensare a dove porteranno queste brillanti osservazioni", ha detto Tell.