Kuinka rakentaa suuri alkuluku | Quanta-lehti

Alkuluvut ovat hankalia asioita. Opimme koulussa, että ne ovat lukuja, joissa ei ole muita tekijöitä kuin 1 ja he itse, ja että matemaatikot ovat tienneet tuhansia vuosia, että niitä on olemassa ääretön määrä. Sellaisen tuottaminen käskystä ei näytä siltä, ​​että sen pitäisi olla vaikeaa.

Mutta se on. Satunnaisen suurten alkulukujen rakentaminen on huomattavan monimutkaista. Sinulla on periaatteessa kaksi laskentavaihtoehtoa, molemmissa on haittoja. Voit käyttää satunnaisuutta ja löytää sellaisen arvaamalla, mutta menetelmä on epäjohdonmukainen – vaarana on luoda eri alkuluku joka kerta. Tai voit käyttää luotettavampaa, determinististä algoritmia, mutta kalliilla laskentakustannuksilla.

Toukokuussa tietojenkäsittelytieteilijöiden ryhmä osoittivat että eräänlainen hybridilähestymistapa voisi myös toimia. He julkaisivat algoritmin, joka yhdistää tehokkaasti satunnaiset ja deterministiset lähestymistavat tietynpituisen alkuluvun tulostamiseksi suurella todennäköisyydellä, vaikka algoritmi ajettaisiin monta kertaa. Algoritmi yhdistää satunnaisuuden ja monimutkaisuuden mielenkiintoisilla tavoilla, ja se voi olla hyödyllinen myös kryptografiassa, jossa jotkin koodausmenetelmät perustuvat suurten alkulukujen rakentamiseen.

"He laativat sarjan yrityksiä, joista jokainen yritti muodostaa eripituisen alkuluvun, ja osoittivat, että yksi yrityksistä toimii", sanoi Roei Tell, teoreettinen tietojenkäsittelytieteilijä Institute for Advanced Studyssa, joka ei ollut mukana työhön. "Se on rakenne, joka tuottaa deterministisesti valitun alkuluvun, mutta antaa sinun heittää kolikoita ja tehdä satunnaisia ​​valintoja prosessin aikana."

Tehokkaan prime-reseptin valmistamisen haasteella on syvät juuret. "Emme todellakaan tiedä niin paljon alkulukujen jakautumisesta tai alkulukujen aukoista", sanoi näennäissatunnaisia ​​algoritmeja tutkiva Ofer Grossman. Ja jos emme tiedä mistä niitä löytää, ei ole helppoa tapaa luoda alkulukua tyhjästä.

Ajan myötä tutkijat kehittivät edellä mainitut lähestymistavat. Yksinkertaisin tapa on vain arvata. Jos haluat esimerkiksi alkuluvun, jossa on 1,000 numeroa, voit valita satunnaisesti 1,000-numeroisen luvun ja tarkistaa sen. "Jos se ei ole ensiluokkainen, kokeile vain toista, toista ja niin edelleen, kunnes löydät sellaisen", sanoi Rahul Santanam, tietojenkäsittelytieteilijä Oxfordin yliopistosta ja uuden paperin toinen kirjoittaja. "Koska alkulukuja on monia, tämä algoritmi antaa sinulle luvun, joka on alkuluku suurella todennäköisyydellä suhteellisen pienen iteraatiomäärän jälkeen." Mutta satunnaisuuden käyttäminen tarkoittaa, että saat todennäköisesti eri numeron joka kerta, hän sanoi. Se voi olla ongelma, jos tarvitset johdonmukaisuutta – jos esimerkiksi käytät salausmenetelmää, joka riippuu suurten alkulukujen saatavuudesta.

Toinen lähestymistapa on käyttää determinististä algoritmia. Voit valita aloituspisteen ja alkaa testata numeroita peräkkäin primaalisuuden varalta. Lopulta sinun on määrä löytää sellainen, ja algoritmisi tulostaa jatkuvasti ensimmäisen löytämäsi. Mutta se voi kestää hetken: jos etsit 1,000 numeroa sisältävää alkulukua, jopa laskutoimitusta kahdella⁵⁰⁰ askeleet – jotka vievät paljon kauemmin kuin maailmankaikkeuden ikä – eivät riitä takaamaan menestystä.

Vuonna 2009 matemaatikko ja Fields-mitalisti Terence Tao halusi menestyä paremmin. Hän haastoi matemaatikot keksimään deterministisen algoritmin tietyn kokoisen alkuluvun löytämiseksi laskennallisen aikarajan sisällä.

Tätä aikarajaa kutsutaan polynomiajaksi. Algoritmi ratkaisee ongelman polynomiajassa, jos sen suorittamien vaiheiden määrä on korkeintaan polynomifunktio n, syötteen koko. (Polynomifunktio sisältää termejä, joiden muuttujat on korotettu positiivisiin kokonaislukupotenssiin, kuten n² tai 4n³.) Alkulukukonstruktion yhteydessä n viittaa haluamasi alkuluvun numeroiden määrään. Laskennallisesti tämä ei maksa paljoa: Tietojenkäsittelytieteilijät kuvailevat ongelmia, jotka voidaan ratkaista algoritmeilla polynomiajassa. Vaikea ongelma sitä vastoin vie eksponentiaalista aikaa, mikä tarkoittaa, että se vaatii useita vaiheita, jotka on approksimoitu eksponentiaalisella funktiolla (joka sisältää termit kuten 2ⁿ).

Vuosikymmenten ajan tutkijat ovat tutkineet satunnaisuuden ja kovuuden välistä yhteyttä. Alkulukujen muodostamisongelmaa pidettiin helpona, jos sallit satunnaisuuden – ja tyytyi saamaan joka kerta eri numero – ja vaikeaksi, jos vaadit determinismia.

Kukaan ei ole vielä onnistunut vastaamaan Taon haasteeseen, mutta uusi työ tulee lähelle. Se perustuu vahvasti Massachusetts Institute of Technologyn tietotekniikan tutkijoiden Shafi Goldwasserin ja Eran Gatin vuonna 2011 käyttöön ottamaan lähestymistapaan. He kuvasivat "pseudodeterministisiä" algoritmeja – matemaattisia reseptejä hakuongelmiin, kuten suurten alkulukujen löytämiseen, jotka voisivat hyödyntää satunnaisuuden edut ja suurella todennäköisyydellä silti tuottaa saman vastauksen joka kerta. He käyttäisivät reseptin satunnaisten bittien tehokkuutta, jotka determinisoituisivat tuloksessa ja näyttäisivät deterministisiltä.

Tutkijat ovat tutkineet pseudodeterministisiä algoritmeja siitä lähtien. Vuonna 2017 Santhanam ja Igor Oliveira Warwickin yliopistosta (joka myös osallistui uuteen teokseen) on kuvattu pseudodeterministinen lähestymistapa alkulukujen rakentamiseen, joka käytti satunnaisuutta ja näytti vakuuttavasti deterministisiltä, ​​mutta se toimi "subeksponentiaalisessa" ajassa - nopeammin kuin eksponentiaalinen, mutta hitaammin kuin polynomiaika. Sitten vuonna 2021 Tell and Lijie Chen, tietojenkäsittelytieteilijä Kalifornian yliopistossa Berkeleyssä, tutkitaan kuinka kovan ongelman avulla rakennetaan näennäissatunnaisten lukujen generaattori (algoritmi, joka luo lukujonon, jota ei voi erottaa satunnaistulosta). "[Löysimme] uuden yhteyden kovuuden ja näennäissatunnaisuuden välillä", Chen sanoi.

Lopulta palaset yhdistyivät keväällä 2023, aikana laskennallisen monimutkaisuuden bootcamp Simons Institute for the Theory of Computing Berkeleyssä, kun tutkijat alkoivat työskennellä yhdessä ongelman parissa kutomalla yhteen aiempia tuloksia. Uutta työtä varten, Chen sanoi, Hanlin Renillä - Oxfordin tietojenkäsittelytieteilijällä ja kirjoittajalla - oli ensimmäiset ideat yhdistää Chen-Tell-tulos Santhanam-Oliveiran lähestymistapaan uudella tavalla. Sitten koko tiimi kehitti ideoita täydellisemmin uuden paperin tuottamiseksi.

Tuloksena oleva pseudodeterministinen algoritmi, Santhanam sanoi, käytti uusia tapoja tarkastella menneitä töitä tuottaakseen alkulukuja polynomiajassa. Se käytti todistetusti satunnaisuutta tietynpituisen alkuluvun tulostamiseen, ja työkalu on tarkempi kuin satunnainen arvaus ja laskennallisesti tehokkaampi kuin deterministinen murskaus.

Uusi algoritmi on myös huomattavan yksinkertainen, Santhanam sanoi, ja sitä voidaan soveltaa monenlaisiin hakuongelmiin - oikeastaan ​​mihin tahansa tiheään lukujen osajoukkoon, kuten alkuluvut, joiden jäsenyys voidaan määrittää polynomiajassa. Mutta se ei ole täydellinen. Algoritmi toimii äärettömän monelle syötepituudelle, mutta se ei kata kaikkia numeroiden pituuksia. Joitakin arvoja saattaa silti olla n siellä, jolle algoritmi ei deterministisesti tuota alkulukua.

"Olisi siistiä päästä eroon tuosta pienestä varoituksesta", Grossman sanoi.

Lopullinen tavoite, Santhanam sanoi, on löytää algoritmi, joka ei vaadi satunnaisuutta ollenkaan. Mutta se tavoite on edelleen avoinna. "Haluamme käyttää determinismia", hän sanoi.

Mutta hän huomautti myös, että näennäissatunnaiset prosessit ovat tehokkaita työkaluja, ja projektit, kuten alkulukujen rakentaminen, ovat vain yksi tapa käyttää niitä matematiikan, tietojenkäsittelytieteen, informaatioteorian ja muiden alojen ideoiden yhdistämiseen.

"On jännittävää yrittää ajatella, mihin muualle nämä loistavat havainnot johtavat", Tell sanoi.