Sådan opbygger du et stort primtal | Quanta Magasinet

Primtal er vanskelige ting. Vi lærer i skolen, at det er tal uden andre faktorer end 1 og dem selv, og at matematikere har vidst i tusinder af år, at der findes et uendeligt antal af dem. At producere en på kommando virker ikke som om det skulle være svært.

Men det er. At konstruere vilkårligt store primtal er bemærkelsesværdigt kompliceret. Du har grundlæggende to beregningsmuligheder, begge med ulemper. Du kan bruge tilfældighed og finde en ved at gætte, men metoden er inkonsekvent - du risikerer at generere en anden prime hver gang. Eller du kunne bruge en mere pålidelig, deterministisk algoritme, men til en høj beregningsomkostning.

I maj, et hold af dataloger viste at en slags hybrid tilgang også kunne fungere. De udgav en algoritme, der effektivt kombinerer de tilfældige og deterministiske tilgange til at udlæse et primtal af en specifik længde, med en høj sandsynlighed for at levere den samme, selvom algoritmen køres mange gange. Algoritmen forbinder tilfældighed og kompleksitet på interessante måder, og den kan også være nyttig til kryptografi, hvor nogle kodningsskemaer er afhængige af konstruktionen af ​​store primtal.

"De opstillede en sekvens af forsøg, hver af dem forsøgte at konstruere et primtal af forskellig længde, og viste, at et af forsøgene virker," sagde Roei Fortæl, en teoretisk datamatiker ved Institute for Advanced Study, som ikke var involveret i arbejdet. "Det er en konstruktion, der udsender et deterministisk valgt primtal, men giver dig mulighed for at kaste mønter og træffe tilfældige valg i processen."

Udfordringen med at lave en effektiv opskrift på primer har dybe rødder. "Vi ved virkelig ikke så meget om, hvordan primtal er fordelt, eller om huller i primtal," sagde Ofer Grossman, der studerer pseudorandom-algoritmer. Og hvis vi ikke ved, hvor vi kan finde dem, er der ingen nem måde at generere et primtal fra bunden.

Over tid udviklede forskere de førnævnte tilgange. Den enkleste måde er bare at gætte. Hvis du vil have et primtal med 1,000 cifre, for eksempel, kan du vælge et 1,000-cifret tal tilfældigt og derefter kontrollere det. "Hvis det ikke er prime, prøver du bare en anden, og en anden, og så videre, indtil du finder en," sagde Rahul Santhanam, en datalog ved University of Oxford og medforfatter til det nye papir. "Fordi der er mange primtal, vil denne algoritme give dig et tal, der er primtal med stor sandsynlighed, efter et relativt lille antal iterationer." Men at bruge tilfældighed betyder, at du sandsynligvis vil få et andet tal hver gang, sagde han. Det kan være et problem, hvis du har brug for konsistens - hvis du f.eks. bruger en kryptografisk sikkerhedsmetode, der afhænger af tilgængeligheden af ​​store primtal.

Den anden tilgang er at gå med en deterministisk algoritme. Du kan vælge et udgangspunkt og begynde at teste tal sekventielt for primært. Til sidst er du bestemt til at finde en, og din algoritme vil konsekvent udlæse den første, du finder. Men det kan tage et stykke tid: Hvis du leder efter et primtal med 1,000 cifre, endda en beregning med 2⁵⁰⁰ trin - som ville tage meget længere tid end universets alder - er ikke nok til at garantere succes.

I 2009 ønskede matematikeren og Fields-medaljevinderen Terence Tao at gøre det bedre. Han udfordrede matematikere til at komme med en deterministisk algoritme til at finde et primtal af en given størrelse inden for en beregningstidsgrænse.

Denne tidsgrænse er kendt som polynomiel tid. En algoritme løser et problem i polynomiel tid, hvis antallet af trin den tager ikke er mere end en polynomiel funktion af n, størrelsen af ​​input. (En polynomisk funktion inkluderer termer, der har variable hævet til positive heltalspotenser, som f n² eller 4n³.) I forbindelse med primtalskonstruktion, n henviser til antallet af cifre i det primtal, du ønsker. Beregningsmæssigt koster dette ikke meget: Dataloger beskriver problemer, der kan løses ved hjælp af algoritmer i polynomisk tid, som let. Et hårdt problem tager derimod eksponentiel tid, hvilket betyder, at det kræver et antal trin tilnærmet af en eksponentiel funktion (som inkluderer udtryk som 2ⁿ).

I årtier har forskere undersøgt sammenhængen mellem tilfældighed og hårdhed. Primtalskonstruktionsproblemet blev betragtet som let, hvis man tillod tilfældighed - og var tilfreds med at modtage et andet tal hver gang - og svært, hvis man insisterede på determinisme.

Ingen har formået at møde Taos udfordring endnu, men det nye arbejde kommer tæt på. Den trækker i høj grad på en tilgang introduceret i 2011 af Shafi Goldwasser og Eran Gat, dataloger ved Massachusetts Institute of Technology. De beskrev "pseudodeterministiske" algoritmer - matematiske opskrifter på søgeproblemer, som at finde store primtal, der kunne udnytte fordelene ved tilfældighed og med stor sandsynlighed stadig producere det samme svar hver gang. De ville bruge effektiviteten af ​​tilfældige bits i opskriften, som ville blive de-randomiseret i resultatet, hvilket virkede deterministisk.

Forskere har udforsket pseudodeterministiske algoritmer lige siden. I 2017, Santhanam og Igor Oliveira fra University of Warwick (som også bidrog til det nye arbejde) beskrevet en pseudodeterministisk tilgang til at konstruere primtal, der brugte tilfældighed og så overbevisende deterministisk ud, men den virkede i "subeksponentiel" tid - hurtigere end eksponentiel, men langsommere end polynomiel tid. Så i 2021, Fortæl og Lijie Chen, en datalog ved University of California, Berkeley, udforsket hvordan man bruger et hårdt problem til at bygge en pseudorandom-talgenerator (en algoritme, der genererer en række tal, der ikke kan skelnes fra et tilfældigt output). "[Vi] fandt en ny forbindelse mellem hårdhed og pseudorandomness," sagde Chen.

Stykkerne kom endelig sammen i foråret 2023, under en bootcamp om beregningsmæssig kompleksitet ved Simons Institute for the Theory of Computing i Berkeley, da forskerne begyndte at arbejde sammen om problemet og flette tidligere resultater sammen. Til det nye arbejde, sagde Chen, havde Hanlin Ren - en datalog ved Oxford og en medforfatter - de første ideer til at kombinere Chen-Tell-resultatet med Santhanam-Oliveira-tilgangen på en ny måde. Derefter udviklede hele teamet ideerne mere fuldstændigt til at producere det nye papir.

Den resulterende pseudodeterministiske algoritme, sagde Santhanam, brugte nye måder at se på tidligere arbejde til at producere primtal i polynomisk tid. Det brugte beviseligt tilfældighed til at udskrive et primtal af en specifik længde, og værktøjet er mere nøjagtigt end tilfældig gæt og mere beregningsmæssigt effektivt end deterministisk knas.

Den nye algoritme er også bemærkelsesværdig enkel, sagde Santhanam, og den kan anvendes på en lang række søgeproblemer - i virkeligheden til enhver tæt delmængde af tal, som primtal, for hvilke medlemskab kan bestemmes i polynomisk tid. Men det er ikke perfekt. Algoritmen fungerer for uendeligt mange inputlængder, men den dækker ikke alle længder af cifre. Der kan stadig være nogle værdier af n derude, som algoritmen ikke deterministisk producerer et primtal for.

"Det ville være fedt at slippe af med den lille advarsel," sagde Grossman.

Det ultimative mål, sagde Santhanam, er at finde en algoritme, der overhovedet ikke kræver tilfældighed. Men den søgen forbliver åben. "Determinisme er det, vi gerne vil bruge," sagde han.

Men han påpegede også, at pseudorandom-processer er kraftfulde værktøjer, og projekter som at konstruere primtal er blot én måde at bruge dem til at forbinde ideer fra matematik, datalogi, informationsteori og andre områder.

"Det er spændende at prøve at tænke, hvor disse strålende observationer ellers vil føre hen," sagde Tell.