Hoe een groot priemgetal te bouwen | Quanta-tijdschrift

Priemgetallen zijn lastige dingen. We leren op school dat het getallen zijn zonder andere factoren dan 1 en zichzelf, en dat wiskundigen al duizenden jaren weten dat er een oneindig aantal bestaat. Een op commando produceren lijkt niet moeilijk te zijn.

Maar het is. Het construeren van willekeurig grote priemgetallen is opmerkelijk gecompliceerd. Je hebt in feite twee rekenopties, beide met nadelen. Je zou willekeur kunnen gebruiken en er een vinden door te raden, maar de methode is inconsistent - je loopt het risico elke keer een ander priemgetal te genereren. Of u kunt een betrouwbaarder, deterministisch algoritme gebruiken, maar tegen hoge rekenkosten.

In mei heeft een team van computerwetenschappers vertoonde dat een soort hybride aanpak ook zou kunnen werken. Ze publiceerden een algoritme dat de willekeurige en deterministische benaderingen effectief combineert om een ​​priemgetal van een specifieke lengte uit te voeren, met een grote kans om hetzelfde te leveren, zelfs als het algoritme vele malen wordt uitgevoerd. Het algoritme verbindt willekeur en complexiteit op interessante manieren, en het kan ook nuttig zijn voor cryptografie, waar sommige coderingsschema's afhankelijk zijn van de constructie van grote priemgetallen.

"Ze legden een reeks pogingen neer, elk van hen probeerde een priemgetal van een verschillende lengte te construeren, en toonden aan dat een van de pogingen werkt," zei Roei Tell, een theoretisch computerwetenschapper aan het Institute for Advanced Study die niet bij het werk betrokken was. "Het is een constructie die een deterministisch gekozen priemgetal oplevert, maar waarmee je munten kunt opgooien en willekeurige keuzes kunt maken."

De uitdaging om een ​​efficiënt recept voor priemgetallen te maken heeft diepe wortels. "We weten echt niet zo veel over hoe priemgetallen worden verdeeld, of over hiaten in priemgetallen", zegt Ofer Grossman, die pseudowillekeurige algoritmen bestudeert. En als we niet weten waar we ze kunnen vinden, is er geen gemakkelijke manier om vanaf nul een priemgetal te genereren.

In de loop van de tijd ontwikkelden onderzoekers de bovengenoemde benaderingen. De eenvoudigste manier is gewoon raden. Als u bijvoorbeeld een priemgetal met 1,000 cijfers wilt, kunt u willekeurig een getal van 1,000 cijfers kiezen en dit vervolgens controleren. "Als het geen priemgetal is, probeer je gewoon een andere, en nog een, enzovoort, totdat je er een vindt", zei hij Rahul Santhanam, een computerwetenschapper aan de Universiteit van Oxford en co-auteur van het nieuwe artikel. "Omdat er veel priemgetallen zijn, geeft dit algoritme je na een relatief klein aantal iteraties een getal dat met een hoge waarschijnlijkheid een priemgetal is." Maar het gebruik van willekeur betekent dat je waarschijnlijk elke keer een ander nummer krijgt, zei hij. Dat kan een probleem zijn als je consistentie nodig hebt - als je bijvoorbeeld een cryptografische beveiligingsmethode gebruikt die afhankelijk is van de beschikbaarheid van grote priemgetallen.

De andere benadering is om te gaan met een deterministisch algoritme. Je zou een startpunt kunnen kiezen en beginnen met het achtereenvolgens testen van nummers voor primaliteit. Uiteindelijk ben je voorbestemd om er een te vinden, en je algoritme zal consequent de eerste die je vindt uitvoeren. Maar het kan even duren: als je op zoek bent naar een priemgetal met 1,000 cijfers, zelfs een berekening met 2⁵⁰⁰ stappen - die veel langer zouden duren dan de leeftijd van het universum - is niet genoeg om succes te garanderen.

In 2009 wilde de wiskundige en Fields-medaillewinnaar Terence Tao het beter doen. Hij daagde wiskundigen uit om een ​​deterministisch algoritme te bedenken voor het vinden van een priemgetal van een bepaalde grootte binnen een rekentijdlimiet.

Die tijdslimiet staat bekend als polynomiale tijd. Een algoritme lost een probleem in polynoomtijd op als het aantal stappen dat het neemt niet meer is dan een polynoomfunctie van n, de grootte van de invoer. (Een polynoomfunctie omvat termen waarvan variabelen zijn verheven tot positieve gehele machten, zoals n² of 4n³.) In de context van de constructie van priemgetallen, n verwijst naar het aantal cijfers in het gewenste priemgetal. Computationeel gezien kost dit niet veel: computerwetenschappers beschrijven problemen die door algoritmen in polynoomtijd kunnen worden opgelost als eenvoudig. Een moeilijk probleem daarentegen kost exponentiële tijd, wat betekent dat het een aantal stappen vereist dat wordt benaderd door een exponentiële functie (waaronder termen als 2ⁿ).

Decennialang hebben onderzoekers het verband tussen willekeur en hardheid onderzocht. Het constructieprobleem met priemgetallen werd als gemakkelijk beschouwd als je willekeur toestond - en tevreden was met elke keer een ander getal - en als moeilijk als je aandrong op determinisme.

Het is nog niemand gelukt om de uitdaging van Tao aan te gaan, maar het nieuwe werk komt in de buurt. Het leunt zwaar op een benadering die in 2011 werd geïntroduceerd door Shafi Goldwasser en Eran Gat, computerwetenschappers aan het Massachusetts Institute of Technology. Ze beschreven "pseudodeterministische" algoritmen - wiskundige recepten voor zoekproblemen, zoals het vinden van grote priemgetallen, die de voordelen van willekeur zouden kunnen benutten en, met grote waarschijnlijkheid, toch elke keer hetzelfde antwoord zouden opleveren. Ze zouden de efficiëntie van willekeurige bits in het recept gebruiken, die in de uitkomst gederandomiseerd zouden zijn en deterministisch zouden lijken.

Onderzoekers hebben sindsdien pseudodeterministische algoritmen onderzocht. In 2017, Santhanam en Igor Oliveira van de Universiteit van Warwick (die ook heeft bijgedragen aan het nieuwe werk) beschreven een pseudodeterministische benadering voor het construeren van priemgetallen die willekeurigheid gebruikte en er overtuigend deterministisch uitzag, maar het werkte in "subexponentiële" tijd - sneller dan exponentieel, maar langzamer dan polynomiale tijd. Dan in 2021, Vertel en Liji Chen, een computerwetenschapper aan de University of California, Berkeley, nagegaan hoe een moeilijk probleem te gebruiken om een ​​generator voor pseudowillekeurige getallen te bouwen (een algoritme dat een reeks getallen genereert die niet te onderscheiden is van een willekeurige uitvoer). "[We] vonden een nieuw verband tussen hardheid en pseudowillekeurigheid," zei Chen.

De stukken kwamen uiteindelijk samen in het voorjaar van 2023, tijdens een bootcamp over computationele complexiteit aan het Simons Institute for the Theory of Computing in Berkeley, toen de onderzoekers begonnen samen te werken aan het probleem en resultaten uit het verleden met elkaar verweven. Voor het nieuwe werk, zei Chen, had Hanlin Ren - een computerwetenschapper in Oxford en een co-auteur - de eerste ideeën om het Chen-Tell-resultaat op een nieuwe manier te combineren met de Santhanam-Oliveira-benadering. Daarna werkte het hele team de ideeën vollediger uit om het nieuwe papier te produceren.

Het resulterende pseudodeterministische algoritme, zei Santhanam, gebruikte nieuwe manieren om naar werk uit het verleden te kijken om priemgetallen in polynomiale tijd te produceren. Het heeft aantoonbaar willekeur gebruikt om een ​​priemgetal van een specifieke lengte uit te voeren, en de tool is nauwkeuriger dan willekeurig raden en rekenkundig efficiënter dan deterministisch kraken.

Het nieuwe algoritme is ook opmerkelijk eenvoudig, zei Santhanam, en het kan worden toegepast op een breed scala aan zoekproblemen - eigenlijk op elke dichte subset van getallen, zoals de priemgetallen, waarvoor het lidmaatschap in polynomiale tijd kan worden bepaald. Maar het is niet perfect. Het algoritme werkt voor oneindig veel invoerlengtes, maar dekt niet alle cijferlengtes. Er kunnen nog enkele waarden van n waarvoor het algoritme niet deterministisch een priemgetal produceert.

"Het zou gaaf zijn om van dat kleine voorbehoud af te komen", zei Grossman.

Het uiteindelijke doel, zei Santhanam, is om een ​​algoritme te vinden dat helemaal geen willekeur vereist. Maar die zoektocht blijft open. "Determinisme is wat we zouden willen gebruiken," zei hij.

Maar hij wees er ook op dat pseudowillekeurige processen krachtige hulpmiddelen zijn, en projecten zoals het construeren van priemgetallen zijn slechts één manier om ze te gebruiken om ideeën uit de wiskunde, informatica, informatietheorie en andere gebieden met elkaar te verbinden.

"Het is opwindend om te proberen te bedenken waar deze briljante observaties nog meer toe zullen leiden", zei Tell.