Hvordan bygge et stort primtall | Quanta Magazine

Primtall er vanskelige ting. Vi lærer på skolen at de er tall uten andre faktorer enn 1 og seg selv, og at matematikere har visst i tusenvis av år at det eksisterer et uendelig antall av dem. Å produsere en på kommando virker ikke som om det burde være vanskelig.

Men det er. Å konstruere vilkårlig store primtall er bemerkelsesverdig komplisert. Du har i utgangspunktet to beregningsalternativer, begge med ulemper. Du kan bruke tilfeldighet og finne en ved å gjette, men metoden er inkonsekvent - du risikerer å generere en annen primtall hver gang. Eller du kan bruke en mer pålitelig, deterministisk algoritme, men til en høy beregningskostnad.

I mai, et team av informatikere viste at en slags hybrid tilnærming også kunne fungere. De publiserte en algoritme som effektivt kombinerer de tilfeldige og deterministiske tilnærmingene for å gi ut et primtall med en bestemt lengde, med stor sannsynlighet for å levere den samme selv om algoritmen kjøres mange ganger. Algoritmen forbinder tilfeldighet og kompleksitet på interessante måter, og den kan også være nyttig for kryptografi, der noen kodingsskjemaer er avhengige av konstruksjonen av store primtal.

"De la ut en sekvens av forsøk, hver av dem prøvde å konstruere et primtall med forskjellig lengde, og viste at ett av forsøkene fungerer," sa Roei Fortell, en teoretisk informatiker ved Institute for Advanced Study som ikke var involvert i arbeidet. "Det er en konstruksjon som gir en deterministisk valgt primtall, men lar deg kaste mynter og ta tilfeldige valg i prosessen."

Utfordringen med å lage en effektiv oppskrift på primtall har dype røtter. "Vi vet egentlig ikke så mye om hvordan primtallene er fordelt, eller om hull i primtallene," sa Ofer Grossman, som studerer pseudorandomalgoritmer. Og hvis vi ikke vet hvor vi finner dem, er det ingen enkel måte å generere et primtall fra bunnen av.

Over tid utviklet forskere de nevnte tilnærmingene. Den enkleste måten er bare å gjette. Hvis du vil ha et primtall med 1,000 sifre, for eksempel, kan du velge et 1,000-sifret tall tilfeldig og deretter sjekke det. "Hvis det ikke er prime, prøver du bare en annen, og en annen, og så videre til du finner en," sa Rahul Santhanam, en informatiker ved University of Oxford og medforfatter av den nye artikkelen. "Fordi det er mange primtall, vil denne algoritmen gi deg et tall som er primtall med høy sannsynlighet, etter et relativt lite antall iterasjoner." Men å bruke tilfeldighet betyr at du sannsynligvis vil få et annet tall hver gang, sa han. Det kan være et problem hvis du trenger konsistens - hvis du for eksempel bruker en kryptografisk sikkerhetsmetode som avhenger av tilgjengeligheten av store primtal.

Den andre tilnærmingen er å gå med en deterministisk algoritme. Du kan velge et utgangspunkt og begynne å teste tall, sekvensielt, for primalitet. Til slutt er du bestemt til å finne en, og algoritmen din vil konsekvent produsere den første du finner. Men det kan ta litt tid: Hvis du leter etter et primtall med 1,000 sifre, til og med en beregning med 2⁵⁰⁰ trinn - som vil ta mye lengre tid enn universets alder - er ikke nok til å garantere suksess.

I 2009 ønsket matematikeren og Fields-medaljevinneren Terence Tao å gjøre det bedre. Han utfordret matematikere til å komme opp med en deterministisk algoritme for å finne en primtall av en gitt størrelse innenfor en beregningstidsgrense.

Denne tidsbegrensningen er kjent som polynomtid. En algoritme løser et problem i polynomtid hvis antall trinn den tar ikke er mer enn en polynomfunksjon av n, størrelsen på inngangen. (En polynomfunksjon inkluderer termer som har variabler hevet til positive heltallspotter, som n² eller 4n³.) I sammenheng med primtallskonstruksjon, n refererer til antall sifre i primtall du ønsker. Beregningsmessig sett koster ikke dette mye: Dataforskere beskriver problemer som kan løses ved hjelp av algoritmer i polynomisk tid som enkelt. Et vanskelig problem tar derimot eksponentiell tid, noe som betyr at det krever et antall trinn tilnærmet av en eksponentiell funksjon (som inkluderer termer som 2ⁿ).

I flere tiår har forskere undersøkt sammenhengen mellom tilfeldighet og hardhet. Konstruksjonsproblemet med primtall ble ansett som enkelt hvis du tillot tilfeldighet - og var fornøyd med å motta et annet tall hver gang - og vanskelig hvis du insisterte på determinisme.

Ingen har klart å møte Taos utfordring ennå, men det nye arbeidet nærmer seg. Den trekker mye på en tilnærming introdusert i 2011 av Shafi Goldwasser og Eran Gat, dataforskere ved Massachusetts Institute of Technology. De beskrev "pseudodeterministiske" algoritmer - matematiske oppskrifter for søkeproblemer, som å finne store primtall, som kan utnytte fordelene ved tilfeldighet og, med høy sannsynlighet, fortsatt produsere det samme svaret hver gang. De ville bruke effektiviteten til tilfeldige biter i oppskriften, som ville bli de-randomisert i utfallet, og virke deterministisk.

Forskere har utforsket pseudodeterministiske algoritmer siden den gang. I 2017, Santhanam og Igor Oliveira fra University of Warwick (som også bidro til det nye arbeidet) beskrevet en pseudodeterministisk tilnærming til å konstruere primtall som brukte tilfeldighet og så overbevisende deterministisk ut, men den fungerte i "subeksponentiell" tid - raskere enn eksponentiell, men langsommere enn polynomtid. Så i 2021, Tell og Lijie Chen, en informatiker ved University of California, Berkeley, utforsket hvordan bruke et vanskelig problem for å bygge en pseudorandom tallgenerator (en algoritme som genererer en rekke tall som ikke kan skilles fra en tilfeldig utgang). "[Vi] fant en ny sammenheng mellom hardhet og pseudorandomness," sa Chen.

Brikkene kom endelig sammen våren 2023, under en bootcamp om beregningsmessig kompleksitet ved Simons Institute for Theory of Computing i Berkeley, da forskerne begynte å jobbe sammen om problemet og veve sammen tidligere resultater. For det nye arbeidet, sa Chen, hadde Hanlin Ren - en informatiker ved Oxford og en medforfatter - de første ideene om å kombinere Chen-Tell-resultatet med Santhanam-Oliveira-tilnærmingen på en ny måte. Så utviklet hele teamet ideene mer fullstendig for å produsere det nye papiret.

Den resulterende pseudodeterministiske algoritmen, sa Santhanam, brukte nye måter å se på tidligere arbeid for å produsere primtall i polynomtid. Den brukte beviselig tilfeldighet for å gi ut et primtall med en spesifikk lengde, og verktøyet er mer nøyaktig enn tilfeldig gjetting og mer beregningsmessig effektivt enn deterministisk knusing.

Den nye algoritmen er også bemerkelsesverdig enkel, sa Santhanam, og den kan brukes på et bredt spekter av søkeproblemer - egentlig til enhver tett delmengde av tall, som primtall, som medlemskap kan bestemmes for i polynomtid. Men det er ikke perfekt. Algoritmen fungerer for uendelig mange inndatalengder, men den dekker ikke alle lengder av siffer. Det kan fortsatt være noen verdier av n der ute som algoritmen ikke deterministisk produserer en primtall for.

"Det ville vært kult å bli kvitt det lille forbeholdet," sa Grossman.

Det endelige målet, sa Santhanam, er å finne en algoritme som ikke krever tilfeldighet i det hele tatt. Men den søken forblir åpen. "Determinisme er det vi ønsker å bruke," sa han.

Men han påpekte også at pseudorandom-prosesser er kraftige verktøy, og prosjekter som å konstruere primtall er bare én måte å bruke dem til å koble sammen ideer fra matematikk, informatikk, informasjonsteori og andre områder.

"Det er spennende å prøve å tenke hvor ellers disse strålende observasjonene vil føre," sa Tell.