Hogyan készítsünk nagy prímszámot | Quanta Magazin

A prímszámok trükkös dolgok. Az iskolában megtanuljuk, hogy ezek olyan számok, amelyekben nincs más tényező, mint 1 és önmaguk, és hogy a matematikusok évezredek óta tudják, hogy végtelen sok létezik belőlük. Egyet parancsra létrehozni nem úgy tűnik, hogy nehéznek kellene lennie.

De ez. Tetszőlegesen nagy prímszámok megalkotása rendkívül bonyolult. Alapvetően két számítási lehetőséged van, mindkettőnek vannak hátrányai. Használhatja a véletlenszerűséget, és találgatással találhat egyet, de a módszer nem konzisztens – fennáll annak a veszélye, hogy minden alkalommal más prímet generál. Vagy használhat egy megbízhatóbb, determinisztikus algoritmust, de jelentős számítási költséggel.

Májusban egy informatikus csapat kimutatta, hogy egyfajta hibrid megközelítés is működhet. Kiadtak egy algoritmust, amely hatékonyan kombinálja a véletlenszerű és a determinisztikus megközelítéseket, hogy egy meghatározott hosszúságú prímszámot adjon ki, és nagy valószínűséggel ugyanazt adja, még akkor is, ha az algoritmust sokszor futtatják. Az algoritmus érdekes módon köti össze a véletlenszerűséget és a bonyolultságot, és hasznos lehet a kriptográfiában is, ahol egyes kódolási sémák nagy prímszámok felépítésére támaszkodnak.

„Kísérletek sorozatát határozták meg, mindegyikük különböző hosszúságú prímszámot próbált összeállítani, és megmutatta, hogy az egyik próbálkozás működik” – mondta. Roei Tell, az Institute for Advanced Study elméleti informatikusa, aki nem vett részt a munkában. "Ez egy olyan konstrukció, amely determinisztikusan kiválasztott prímet ad ki, de lehetővé teszi érmék feldobását és véletlenszerű választások meghozatalát a folyamat során."

Az alapszínek hatékony receptjének elkészítésének kihívása mélyen gyökerezik. "Valójában nem tudunk sokat a prímszámok eloszlásáról, vagy a prímekben lévő hézagokról" - mondta Ofer Grossman, aki pszeudovéletlen algoritmusokat tanulmányoz. És ha nem tudjuk, hol találjuk őket, nincs egyszerű módja annak, hogy a semmiből prímszámot generáljunk.

Idővel a kutatók kifejlesztették a fent említett megközelítéseket. A legegyszerűbb módja a találgatás. Ha például 1,000 számjegyű prímszámot szeretne, véletlenszerűen válasszon ki egy 1,000 jegyű számot, majd ellenőrizze. "Ha nem elsőrangú, csak próbálj ki egy másikat, és még egyet, és így tovább, amíg meg nem találod" - mondta. Rahul Santhanam, az Oxfordi Egyetem informatikusa és az új tanulmány társszerzője. "Mivel sok prím van, ez az algoritmus viszonylag kis számú iteráció után nagy valószínűséggel ad néhány prímszámot." De a véletlenszerűség használata azt jelenti, hogy valószínűleg minden alkalommal más számot kap, mondta. Ez gondot jelenthet, ha konzisztenciára van szüksége – ha például olyan titkosítási módszert alkalmaz, amely a nagy prímszámok elérhetőségétől függ.

A másik megközelítés a determinisztikus algoritmus alkalmazása. Kiválaszthat egy kiindulási pontot, és elkezdheti a számok szekvenciális tesztelését az elsődlegesség szempontjából. Végül meg kell találnia egyet, és az algoritmusa következetesen az első talált példányt adja ki. De ez eltarthat egy ideig: ha 1,000 számjegyű prímszámot keres, még egy 2-es számítást is⁵⁰⁰ lépések – amelyek sokkal tovább tartanának, mint az univerzum kora – nem elegendőek a sikerhez.

2009-ben a matematikus és a Fields-érmes Terence Tao jobbat akart csinálni. Arra kérte a matematikusokat, hogy dolgozzanak ki egy determinisztikus algoritmust egy adott méretű prím megtalálására egy számítási időhatáron belül.

Ezt az időkorlátot polinomiális időnek nevezik. Egy algoritmus akkor old meg egy problémát polinomiális időben, ha a lépések száma nem több, mint egy polinomiális függvény. n, a bemenet mérete. (A polinomiális függvények olyan kifejezéseket tartalmaznak, amelyek változói pozitív egész hatványra vannak emelve, mint pl n² vagy 4n³.) Prímszám-szerkesztéssel összefüggésben, n a kívánt prím számjegyeinek számát jelenti. Számítási szempontból ez nem kerül sokba: az informatikusok olyan egyszerű problémákat írnak le, amelyek algoritmusokkal polinomiális időben megoldhatók. Ezzel szemben egy nehéz feladat exponenciális időt vesz igénybe, ami azt jelenti, hogy számos lépésre van szükség, amelyeket egy exponenciális függvény közelít (amely olyan kifejezéseket tartalmaz, mint például a 2ⁿ).

A kutatók évtizedek óta vizsgálják a véletlenszerűség és a keménység közötti összefüggést. A prímszám-szerkesztési problémát könnyűnek tartották, ha megengedi a véletlenszerűséget – és elégedett volt azzal, hogy minden alkalommal más számot kap –, és nehéznek, ha ragaszkodott a determinizmushoz.

Tao kihívásának még senkinek nem sikerült megfelelnie, de az új munka közeledik. Erősen támaszkodik Shafi Goldwasser és Eran Gat, a Massachusetts Institute of Technology informatikusai által 2011-ben bevezetett megközelítésre. „pszeudodeterminisztikus” algoritmusokat írtak le – olyan keresési problémák matematikai receptjeit, mint például a nagy prímszámok megtalálása, amelyek kihasználhatják a véletlenszerűség előnyeit, és nagy valószínűséggel mindig ugyanazt a választ adják. A receptben szereplő véletlenszerű bitek hatékonyságát használnák, amelyek determinisztikusnak tűnnének az eredményben.

A kutatók azóta is pszeudodeterminisztikus algoritmusokat kutatnak. 2017-ben Santhanam és Igor Oliveira a Warwicki Egyetemről (aki szintén közreműködött az új munkában) leírt pszeudodeterminisztikus megközelítés a prímszámok megalkotására, amely véletlenszerűséget használt, és meggyőzően determinisztikusnak tűnt, de „szubexponenciális” időben működött – gyorsabban, mint exponenciális, de lassabban, mint a polinomiális idő. Aztán 2021-ben a Tell és Lijie Chen, a Kaliforniai Egyetem informatikusa, Berkeley, feltárt hogyan lehet egy nehéz feladat segítségével felépíteni egy pszeudovéletlen számgenerátort (olyan algoritmust, amely egy véletlen kimenettől megkülönböztethetetlen számsort generál). "Új összefüggést találtunk a keménység és a pszeudovéletlenség között" - mondta Chen.

A darabok végül 2023 tavaszán álltak össze, közben bootcamp a számítási bonyolultságról a Simons Institute for the Theory of Computing Berkeley-ben, amikor a kutatók együtt kezdtek dolgozni a problémán, összefonva a múlt eredményeit. Chen elmondta, hogy az új munkához Hanlin Rennek – egy oxfordi informatikusnak és egy társszerzőnek – volt a kezdeti ötlete, hogy a Chen-Tell eredményt újszerű módon ötvözze a Santhanam-Oliveira megközelítéssel. Ezután az egész csapat még jobban kidolgozta az ötleteket az új lap elkészítéséhez.

Az eredményül kapott pszeudodeterminisztikus algoritmus – mondta Santhanam – új módszereket használt a múltbeli munkára, hogy prímszámokat állítson elő polinomiális időben. Bizonyíthatóan a véletlenszerűséget használta egy meghatározott hosszúságú prímszám kiadására, és az eszköz pontosabb, mint a véletlenszerű találgatás, és számításilag hatékonyabb, mint a determinisztikus csikorgás.

Az új algoritmus emellett rendkívül egyszerű, mondta Santhanam, és a keresési problémák széles skálájára alkalmazható – valójában a számok bármely sűrű részhalmazára, például a prímekre, amelyekhez a tagság polinomiális időben meghatározható. De nem tökéletes. Az algoritmus végtelen sok bemeneti hosszra működik, de nem fedi le a számjegyek minden hosszát. Még mindig lehetnek bizonyos értékek n ott, amelyekre az algoritmus determinisztikusan nem állít elő prímszámot.

„Jó lenne megszabadulni ettől a kis figyelmeztetéstől” – mondta Grossman.

A végső cél – mondta Santhanam – egy olyan algoritmus megtalálása, amelyhez egyáltalán nincs szükség véletlenszerűségre. De ez a küldetés nyitott marad. „A determinizmust szeretnénk használni” – mondta.

De arra is rámutatott, hogy a pszeudovéletlenszerű folyamatok hatékony eszközök, és az olyan projektek, mint a prímszámok megalkotása, csak egy módja annak, hogy ezeket a matematikai, számítástechnikai, információelméleti és más területekről származó ötleteket összekapcsolják.

„Izgalmas megpróbálni elgondolkodni, hová vezetnek még ezek a ragyogó megfigyelések” – mondta Tell.