Cum să construiți un număr prim mare | Revista Quanta

Numerele prime sunt lucruri complicate. Învățăm la școală că sunt numere fără alți factori decât 1 și ei înșiși și că matematicienii știu de mii de ani că există un număr infinit de ele. Producerea unuia la comandă nu pare că ar trebui să fie dificilă.

Dar asta este. Construirea unor numere prime arbitrar mari este remarcabil de complicată. Practic aveți două opțiuni de calcul, ambele cu dezavantaje. Ați putea folosi aleatoriu și găsiți unul ghicind, dar metoda este inconsecventă - riscați să generați un prim diferit de fiecare dată. Sau ați putea folosi un algoritm mai fiabil, determinist, dar cu un cost de calcul ridicat.

În mai, o echipă de informaticieni a arătat că ar putea funcționa și un fel de abordare hibridă. Ei au publicat un algoritm care combină eficient abordările aleatoare și deterministe pentru a scoate un număr prim de o anumită lungime, cu o probabilitate mare de a-l livra pe același, chiar dacă algoritmul este rulat de mai multe ori. Algoritmul conectează aleatorietatea și complexitatea în moduri interesante și ar putea fi, de asemenea, util pentru criptografie, unde unele scheme de codificare se bazează pe construcția de numere prime mari.

„Au stabilit o succesiune de încercări, fiecare dintre ele încercând să construiască un număr prim de o lungime diferită și au arătat că una dintre încercări funcționează”, a spus Roei Tell, un informatician teoretic la Institutul pentru Studii Avansate care nu a fost implicat în lucrare. „Este o construcție care scoate un prim ales determinist, dar vă permite să aruncați monede și să faceți alegeri aleatorii în acest proces.”

Provocarea de a face o rețetă eficientă pentru prime are rădăcini adânci. „Chiar nu știm atât de multe despre modul în care sunt distribuite numerele prime sau despre golurile în numere prime”, a spus Ofer Grossman, care studiază algoritmii pseudoaleatori. Și dacă nu știm unde să le găsim, nu există o modalitate ușoară de a genera un număr prim de la zero.

De-a lungul timpului, cercetătorii au dezvoltat abordările menționate mai sus. Cel mai simplu mod este doar să ghiciți. Dacă doriți un număr prim cu 1,000 de cifre, de exemplu, puteți alege un număr de 1,000 de cifre la întâmplare și apoi să îl verificați. „Dacă nu este prima, încercați încă unul, și altul și așa mai departe până când găsiți unul”, a spus Rahul Santhanam, un informatician la Universitatea din Oxford și coautor al noii lucrări. „Deoarece există multe numere prime, acest algoritm vă va oferi un număr care este prim cu o probabilitate mare, după un număr relativ mic de iterații.” Dar folosirea aleatoriei înseamnă că probabil veți obține un număr diferit de fiecare dată, a spus el. Aceasta ar putea fi o problemă dacă aveți nevoie de consistență - dacă, să zicem, utilizați o metodă criptografică de securitate care depinde de disponibilitatea numerelor prime mari.

Cealaltă abordare este să mergeți cu un algoritm determinist. Puteți alege un punct de plecare și puteți începe să testați numerele, secvenţial, pentru primalitate. În cele din urmă, ești destinat să găsești unul, iar algoritmul tău îl va scoate în mod constant pe primul pe care îl găsești. Dar ar putea dura ceva timp: dacă cauți un număr prim cu 1,000 de cifre, chiar și un calcul cu 2⁵⁰⁰ pașii – care ar dura mult mai mult decât vârsta universului – nu sunt suficienți pentru a garanta succesul.

În 2009, matematicianul și medaliatul Fields Terence Tao a vrut să facă mai bine. El i-a provocat pe matematicieni să vină cu un algoritm determinist pentru a găsi un prim de o dimensiune dată într-o limită de timp de calcul.

Acea limită de timp este cunoscută sub numele de timp polinom. Un algoritm rezolvă o problemă în timp polinomial dacă numărul de pași pe care îi parcurge nu este mai mult decât o funcție polinomială a n, dimensiunea intrării. (O funcție polinomială include termeni care au variabile ridicate la puteri întregi pozitive, cum ar fi n² sau 4n³.) În contextul construcției numerelor prime, n se referă la numărul de cifre din prima dorită. Din punct de vedere computațional, acest lucru nu costă mult: informaticienii descriu probleme care pot fi rezolvate prin algoritmi în timp polinomial ca fiind ușor. O problemă grea, prin contrast, necesită timp exponențial, ceea ce înseamnă că necesită un număr de pași aproximați de o funcție exponențială (care include termeni precum 2ⁿ).

De zeci de ani, cercetătorii au investigat legătura dintre aleatoriu și duritate. Problema construcției numerelor prime a fost considerată ușoară dacă permiteai aleatorie – și erai mulțumit să primești un număr diferit de fiecare dată – și dificilă dacă insistai pe determinism.

Nimeni nu a reușit încă să facă față provocării lui Tao, dar noua lucrare se apropie. Se bazează în mare măsură pe o abordare introdusă în 2011 de Shafi Goldwasser și Eran Gat, informaticieni de la Institutul de Tehnologie din Massachusetts. Ei au descris algoritmi „pseudodeterminiști” – rețete matematice pentru probleme de căutare, cum ar fi găsirea numerelor prime mari, care ar putea valorifica beneficiile aleatoriei și, cu mare probabilitate, să producă în continuare același răspuns de fiecare dată. Ei ar folosi eficiența biților aleatori în rețetă, care ar fi de-aleatoriați în rezultat, apărând determiniști.

De atunci, cercetătorii au explorat algoritmi pseudodeterminiști. În 2017, Santhanam și Igor Oliveira de la Universitatea din Warwick (care au contribuit și ei la noua lucrare) descris o abordare pseudodeterministă pentru construirea numerelor prime care folosea aleatorietatea și părea în mod convingător deterministă, dar a funcționat în timp „subexponențial” - mai rapid decât exponențial, dar mai lent decât timpul polinomial. Apoi, în 2021, Spune și Lijie Chen, un informatician la Universitatea din California, Berkeley, explorat cum să folosiți o problemă dificilă pentru a construi un generator de numere pseudoaleatoare (un algoritm care generează un șir de numere care nu se pot distinge de o ieșire aleatorie). „[Noi] am găsit o nouă legătură între duritate și pseudoaleatorie”, a spus Chen.

Piesele s-au adunat în cele din urmă în primăvara anului 2023, în timpul un bootcamp pe complexitatea computațională la Institutul Simons pentru Teoria Calculului din Berkeley, când cercetătorii au început să lucreze împreună la această problemă, împletind rezultatele din trecut. Pentru noua lucrare, a spus Chen, Hanlin Ren – un informatician la Oxford și un coautor – a avut ideile inițiale de a combina rezultatul Chen-Tell cu abordarea Santhanam-Oliveira într-un mod nou. Apoi întreaga echipă a dezvoltat ideile mai complet pentru a produce noua lucrare.

Algoritmul pseudodeterminist rezultat, a spus Santhanam, a folosit noi moduri de a privi munca trecută pentru a produce numere prime în timp polinomial. Se dovedește că a folosit aleatorietatea pentru a scoate un număr prim de o anumită lungime, iar instrumentul este mai precis decât ghicitul aleatoriu și mai eficient din punct de vedere computațional decât analiza deterministă.

Noul algoritm este, de asemenea, remarcabil de simplu, a spus Santhanam, și poate fi aplicat la o gamă largă de probleme de căutare - într-adevăr, la orice subset dens de numere, cum ar fi numerele prime, pentru care apartenența poate fi determinată în timp polinomial. Dar nu este perfect. Algoritmul funcționează pentru infinit de lungimi de intrare, dar nu acoperă toate lungimile de cifre. S-ar putea să mai existe unele valori ale n acolo pentru care algoritmul nu produce în mod determinist un prim.

„Ar fi grozav să scăpăm de această mică avertizare”, a spus Grossman.

Scopul final, a spus Santhanam, este de a găsi un algoritm care nu necesită deloc aleatorie. Dar această căutare rămâne deschisă. „Determinismul este ceea ce am dori să folosim”, a spus el.

Dar el a subliniat, de asemenea, că procesele pseudoaleatoare sunt instrumente puternice, iar proiecte precum construirea numerelor prime sunt doar o modalitate de a le folosi pentru a conecta idei din matematică, informatică, teoria informației și alte domenii.

„Este interesant să încercăm să ne gândim unde mai vor duce aceste observații strălucitoare”, a spus Tell.