Hur man bygger ett stort primtal | Quanta Magazine

Primtal är knepiga saker. Vi lär oss i skolan att de är tal utan andra faktorer än 1 och sig själva, och att matematiker har vetat i tusentals år att det finns ett oändligt antal av dem. Att producera en på kommando verkar inte som om det borde vara svårt.

Men det är. Att konstruera godtyckligt stora primtal är anmärkningsvärt komplicerat. Du har i princip två beräkningsalternativ, båda med nackdelar. Du kan använda slumpmässighet och hitta en genom att gissa, men metoden är inkonsekvent - du riskerar att generera ett annat primtal varje gång. Eller så kan du använda en mer pålitlig, deterministisk algoritm, men till en hög beräkningskostnad.

I maj, ett team av datavetare visade att ett slags hybridupplägg också skulle kunna fungera. De publicerade en algoritm som effektivt kombinerar de slumpmässiga och deterministiska metoderna för att mata ut ett primtal av en specifik längd, med en hög sannolikhet att leverera samma även om algoritmen körs många gånger. Algoritmen kopplar samman slumpmässighet och komplexitet på intressanta sätt, och den kan också vara användbar för kryptografi, där vissa kodningsscheman är beroende av konstruktionen av stora primtal.

"De lade ut en sekvens av försök, var och en av dem försökte konstruera ett primtal med olika längd, och visade att ett av försöken fungerar," sa Roei Tell, en teoretisk datavetare vid Institutet för avancerade studier som inte var involverad i arbetet. "Det är en konstruktion som ger ett deterministiskt valt primtal, men låter dig kasta mynt och göra slumpmässiga val i processen."

Utmaningen att göra ett effektivt recept på primörer har djupa rötter. "Vi vet verkligen inte så mycket om hur primtal är fördelade, eller om luckor i primtal", säger Ofer Grossman, som studerar pseudoslumpmässiga algoritmer. Och om vi inte vet var vi ska hitta dem finns det inget enkelt sätt att generera ett primtal från början.

Med tiden utvecklade forskare de ovan nämnda tillvägagångssätten. Det enklaste sättet är bara att gissa. Om du till exempel vill ha ett primtal med 1,000 1,000 siffror kan du välja ett XNUMX XNUMX-siffrigt tal slumpmässigt och sedan kontrollera det. "Om det inte är prime, du bara prova en annan, och en annan, och så vidare tills du hittar en," sa Rahul Santhanam, en datavetare vid University of Oxford och medförfattare till den nya artikeln. "Eftersom det finns många primtal kommer den här algoritmen att ge dig ett tal som är primtal med hög sannolikhet, efter ett relativt litet antal iterationer." Men att använda slumpmässighet betyder att du sannolikt kommer att få ett annat nummer varje gång, sa han. Det kan vara ett problem om du behöver konsekvens - om du till exempel använder en kryptografisk säkerhetsmetod som beror på tillgängligheten av stora primtal.

Det andra tillvägagångssättet är att gå med en deterministisk algoritm. Du kan välja en utgångspunkt och börja testa siffror sekventiellt för primalitet. Så småningom är du förutbestämd att hitta en, och din algoritm kommer konsekvent att mata ut den första du hittar. Men det kan ta ett tag: Om du letar efter ett primtal med 1,000 2 siffror, till och med en beräkning med XNUMX⁵⁰⁰ steg – som skulle ta mycket längre tid än universums ålder – är inte tillräckligt för att garantera framgång.

2009 ville matematikern och Fields-medaljören Terence Tao göra det bättre. Han utmanade matematiker att komma med en deterministisk algoritm för att hitta ett primtal av en given storlek inom en beräkningstidsgräns.

Den tidsgränsen kallas polynomtid. En algoritm löser ett problem i polynomtid om antalet steg den tar inte är mer än en polynomfunktion av n, storleken på ingången. (En polynomfunktion inkluderar termer som har variabler upphöjda till positiva heltalspotenser, som n² eller 4n³.) I samband med primtalskonstruktion, n hänvisar till antalet siffror i det primtal du vill ha. Beräkningsmässigt kostar detta inte mycket: Datavetare beskriver problem som kan lösas med algoritmer i polynomtid som enkelt. Ett svårt problem tar däremot exponentiell tid, vilket innebär att det kräver ett antal steg som approximeras av en exponentiell funktion (som inkluderar termer som 2ⁿ).

I decennier har forskare undersökt sambandet mellan slumpmässighet och hårdhet. Primtalskonstruktionsproblemet ansågs enkelt om man tillät slumpmässighet - och var nöjd med att få ett annat tal varje gång - och svårt om man insisterade på determinism.

Ingen har lyckats möta Taos utmaning än, men det nya arbetet kommer nära. Den bygger mycket på ett tillvägagångssätt som introducerades 2011 av Shafi Goldwasser och Eran Gat, datavetare vid Massachusetts Institute of Technology. De beskrev "pseudodeterministiska" algoritmer - matematiska recept för sökproblem, som att hitta stora primtal, som kan utnyttja fördelarna med slumpmässighet och, med hög sannolikhet, fortfarande producera samma svar varje gång. De skulle använda effektiviteten av slumpmässiga bitar i receptet, som skulle avrandomiseras i resultatet, vilket verkar deterministiskt.

Forskare har utforskat pseudodeterministiska algoritmer sedan dess. 2017, Santhanam och Igor Oliveira från University of Warwick (som också bidrog till det nya arbetet) beskriven ett pseudodeterministiskt tillvägagångssätt för att konstruera primtal som använde slumpmässighet och såg övertygande deterministiskt ut, men det fungerade i "subexponentiell" tid - snabbare än exponentiell, men långsammare än polynomtid. Sedan 2021, Tell and Lijie Chen, en datavetare vid University of California, Berkeley, utforskas hur man använder ett svårt problem för att bygga en pseudoslumptalsgenerator (en algoritm som genererar en sträng med tal som inte går att skilja från en slumpmässig utdata). "[Vi] hittade ett nytt samband mellan hårdhet och pseudoslumpmässighet," sa Chen.

Bitarna kom äntligen samman våren 2023, under en bootcamp om beräkningskomplexitet vid Simons Institute for the Theory of Computing i Berkeley, när forskarna började arbeta tillsammans med problemet och vävde samman tidigare resultat. För det nya arbetet, sa Chen, hade Hanlin Ren – en datavetare vid Oxford och en medförfattare – de första idéerna att kombinera Chen-Tell-resultatet med Santhanam-Oliveira-metoden på ett nytt sätt. Sedan utvecklade hela teamet idéerna mer fullständigt för att producera det nya papperet.

Den resulterande pseudodeterministiska algoritmen, sa Santhanam, använde nya sätt att se på tidigare arbete för att producera primtal i polynomtid. Det använde bevisligen slumpmässighet för att mata ut ett primtal av en specifik längd, och verktyget är mer exakt än slumpmässig gissning och mer beräkningseffektivt än deterministisk kritning.

Den nya algoritmen är också anmärkningsvärt enkel, sa Santhanam, och den kan appliceras på ett brett spektrum av sökproblem - egentligen på alla täta delmängder av tal, som primtal, för vilka medlemskap kan bestämmas i polynomtid. Men det är inte perfekt. Algoritmen fungerar för oändligt många inmatningslängder, men den täcker inte alla siffrorslängder. Det kan fortfarande finnas några värden av n där ute som algoritmen inte deterministiskt producerar ett primtal.

"Det skulle vara coolt att bli av med den lilla varningen," sa Grossman.

Det slutliga målet, sa Santhanam, är att hitta en algoritm som inte alls kräver slumpmässighet. Men det uppdraget är fortfarande öppet. "Determinism är vad vi skulle vilja använda," sa han.

Men han påpekade också att pseudoslumpmässiga processer är kraftfulla verktyg, och projekt som att konstruera primtal är bara ett sätt att använda dem för att koppla ihop idéer från matematik, datavetenskap, informationsteori och andra områden.

"Det är spännande att försöka tänka vart annars dessa lysande observationer kommer att leda," sa Tell.