Kako sestaviti veliko praštevilo | Revija Quanta

Praštevila so zapletene stvari. V šoli se učimo, da so to števila brez faktorjev, razen 1 in samih sebe, in da matematiki že tisočletja vedo, da jih obstaja neskončno veliko. Izdelava enega na ukaz se ne zdi težka.

Ampak je. Konstruiranje poljubno velikih praštevil je izjemno zapleteno. V bistvu imate dve računalniški možnosti, obe s pomanjkljivostmi. Lahko bi uporabili naključnost in enega našli z ugibanjem, vendar je metoda nedosledna - tvegate, da boste vsakič ustvarili drugo praštevilo. Lahko pa uporabite bolj zanesljiv, determinističen algoritem, vendar z visokimi računskimi stroški.

Maja ekipa računalničarjev je pokazala, da bi lahko deloval tudi nekakšen hibridni pristop. Objavili so algoritem, ki učinkovito združuje naključne in deterministične pristope za izpis praštevila določene dolžine, z visoko verjetnostjo, da bo zagotovil isto število, tudi če se algoritem izvaja večkrat. Algoritem povezuje naključnost in zapletenost na zanimive načine in je lahko uporaben tudi za kriptografijo, kjer se nekatere sheme kodiranja zanašajo na konstrukcijo velikih praštevil.

"Postavili so zaporedje poskusov, pri čemer je vsak poskušal sestaviti praštevilo drugačne dolžine, in pokazali, da eden od poskusov deluje," je dejal Roei Tell, teoretični informatik na Inštitutu za napredne študije, ki ni bil vključen v delo. "To je konstrukcija, ki izpiše deterministično izbrano praštevilo, vendar vam omogoča metanje kovancev in sprejemanje naključnih odločitev v procesu."

Izziv priprave učinkovitega recepta za primes ima globoke korenine. "Resnično ne vemo toliko o tem, kako so praštevila porazdeljena, ali o vrzeli v praštevilih," je dejal Ofer Grossman, ki preučuje psevdonaključne algoritme. In če ne vemo, kje jih najti, ni preprostega načina za ustvarjanje praštevila iz nič.

Sčasoma so raziskovalci razvili zgoraj omenjene pristope. Najenostavnejši način je samo ugibati. Če na primer želite praštevilo s 1,000 števkami, lahko naključno izberete 1,000-mestno število in ga nato preverite. "Če ni prvovrsten, preprosto poskusite drugega, in še enega, in tako naprej, dokler ne najdete enega," je rekel Rahul Santhanam, računalniški znanstvenik na Univerzi v Oxfordu in soavtor novega prispevka. "Ker je veliko praštevil, vam bo ta algoritem po razmeroma majhnem številu ponovitev dal neko praštevilo z veliko verjetnostjo." Toda uporaba naključnosti pomeni, da boste verjetno vsakič dobili drugo številko, je dejal. To bi lahko bila težava, če potrebujete doslednost - če, recimo, uporabljate kriptografsko metodo varnosti, ki je odvisna od razpoložljivosti velikih praštevil.

Drugi pristop je uporaba determinističnega algoritma. Izberete lahko izhodišče in začnete zaporedoma preizkušati števila za primalnost. Sčasoma vam je usojeno, da ga najdete in vaš algoritem bo dosledno izpisal prvega, ki ga najdete. Vendar lahko traja nekaj časa: če iščete praštevilo s 1,000 ciframi, tudi izračun z 2⁵⁰⁰ korakov - kar bi trajalo veliko dlje od starosti vesolja - ni dovolj za zagotovitev uspeha.

Leta 2009 je matematik in dobitnik Fieldsove medalje Terence Tao želel biti boljši. Matematike je izzval, naj pripravijo deterministični algoritem za iskanje praštevila dane velikosti v računalniški časovni omejitvi.

Ta časovna omejitev je znana kot polinomski čas. Algoritem reši problem v polinomskem času, če število korakov, ki jih opravi, ni več kot polinomska funkcija n, velikost vnosa. (Polinomska funkcija vključuje izraze, ki imajo spremenljivke dvignjene na pozitivne cele potence, na primer n² ali 4n³.) V kontekstu konstrukcije praštevil, n se nanaša na število števk v praštevilu, ki ga želite. Računalniško gledano to ne stane veliko: računalničarji opisujejo probleme, ki jih je mogoče rešiti z algoritmi v polinomskem času, kot enostavne. Nasprotno pa težka težava zahteva eksponentni čas, kar pomeni, da zahteva številne korake, približane z eksponentno funkcijo (ki vključuje izraze, kot je 2ⁿ).

Raziskovalci že desetletja preiskujejo povezavo med naključnostjo in trdoto. Problem konstrukcije praštevil je veljal za lahkega, če ste dovolili naključnost - in ste bili zadovoljni s tem, da ste vsakič prejeli drugo število - in težkega, če ste vztrajali pri determinizmu.

Nihče še ni uspel odgovoriti na Taov izziv, a novo delo je blizu. V veliki meri temelji na pristopu, ki sta ga leta 2011 predstavila Shafi Goldwasser in Eran Gat, računalniška znanstvenika na Tehnološkem inštitutu Massachusetts. Opisali so "psevdodeterministične" algoritme - matematične recepte za težave pri iskanju, kot je iskanje velikih praštevil, ki bi lahko izkoristili prednosti naključnosti in z veliko verjetnostjo še vedno vsakič dali enak odgovor. Uporabili bi učinkovitost naključnih bitov v receptu, ki bi bili v izidu denaključni in videti deterministični.

Raziskovalci od takrat raziskujejo psevdodeterministične algoritme. Leta 2017 sta Santhanam in Igor Oliveira z Univerze Warwick (ki je prav tako prispeval k novemu delu) opisano psevdodeterministični pristop k konstruiranju praštevil, ki je uporabljal naključnost in je bil videti prepričljivo determinističen, vendar je deloval v "subeksponentnem" času - hitreje kot eksponentni, vendar počasneje od polinomskega časa. Nato leta 2021, Povej in Lijie Chen, računalniški znanstvenik na kalifornijski univerzi Berkeley, raziskali kako uporabiti težko težavo za izdelavo generatorja psevdonaključnih števil (algoritem, ki generira niz števil, ki se ne razlikujejo od naključnega izhoda). "Našli smo novo povezavo med trdoto in psevdonaključnostjo," je dejal Chen.

Kosi se končno sestavili spomladi 2023, med bootcamp o računalniški kompleksnosti na Simonsovem inštitutu za teorijo računalništva na Berkeleyju, ko so raziskovalci začeli sodelovati pri problemu in prepletati pretekle rezultate. Za novo delo, je dejal Chen, je imel Hanlin Ren - računalniški znanstvenik na Oxfordu in soavtor - začetne ideje, da bi rezultat Chen-Tell združil s pristopom Santhanam-Oliveira na nov način. Nato je celotna ekipa bolj temeljito razvila ideje za izdelavo novega papirja.

Nastali psevdodeterministični algoritem, je dejal Santhanam, je uporabil nove načine gledanja na preteklo delo za izdelavo praštevil v polinomskem času. Dokazljivo je uporabilo naključnost za izpis praštevila določene dolžine, orodje pa je natančnejše od naključnega ugibanja in računsko učinkovitejše od determinističnega drobljenja.

Novi algoritem je tudi izjemno preprost, je dejal Santhanam, in ga je mogoče uporabiti za širok spekter težav pri iskanju - pravzaprav za katero koli gosto podmnožico števil, kot so praštevila, za katere je mogoče določiti članstvo v polinomskem času. Ampak ni popolno. Algoritem deluje za neskončno veliko vhodnih dolžin, vendar ne pokriva vseh dolžin števk. Morda še obstajajo nekatere vrednosti n tam zunaj, za katerega algoritem deterministično ne proizvede praštevila.

"Kul bi bilo, če bi se znebili tega majhnega opozorila," je dejal Grossman.

Končni cilj, je dejal Santhanam, je najti algoritem, ki sploh ne zahteva naključnosti. Toda to iskanje ostaja odprto. "Determinizem je tisto, kar bi radi uporabili," je dejal.

Poudaril pa je tudi, da so psevdonaključni procesi močna orodja in so projekti, kot je konstruiranje praštevil, le eden od načinov njihove uporabe za povezovanje idej iz matematike, računalništva, informacijske teorije in drugih področij.

"Vznemirljivo je poskušati razmišljati, kam drugam bodo pripeljala ta briljantna opažanja," je dejal Tell.