23 millió jegyű a legnagyobb ismert prímszám

Az effajta vadászat elsőre öncélú kedvtelésnek tűnhet, de nem az.

Két folytonos, soha véget nem érő versenyfutás van a matematikusok és a matematika iránt elkötelezett laikusok között: a pí minél pontosabb (tehát minél több tizedesjegyet tartalmazó) meghatározása, illetve a legnagyobb ismert prímszám megtalálása.

Néhány napja a prímszámokat célzó küldetés járt újabb sikerrel, hiszen egy, az amerikai Tennessee államban élő villamosmérnök rálelt az eddig ismert legnagyobb prímszámra. Bocsássák meg olvasóink, ha most nem közöljük a számot a maga teljességében (terjedelmi korlátaink előtt meghajolva – e cikk körülbelül 6000 karakteres), elégedjenek meg azzal, hogy 4-essel kezdődik, utána következik több mint 23 millió számjegy/karakter, és a vége 1-es.

Felfrissítendő az iskolai matekórán minden bizonnyal elsajátított ismereteinket, prímszámnak nevezzük azt az egynél nagyobb egész számot, amelynek pontosan két osztója van: az 1 és önmaga. Az első néhány prímszám a 2, 3, 5, 7, 11, 13, 17 és így tovább. A prímszámok mindig is elbűvölték a matematikusokat, amióta ez a tudomány létezik.

Ahogy haladunk az egyre nagyobb számok felé, egyre ritkábbak lesznek a prímek, ugyanakkor végtelen sok prímszám van. Ennek az állításnak a legrégibb bizonyítását Euklidész adta meg Elemek című munkájában.

Sok matematikus egész élete munkáját áldozta arra, hogy szabályszerűséget találjon a prímek előfordulásában. Nem voltak képesek elhinni ugyanis, hogy a máskülönben szinte isteni eredetűnek tűnő tulajdonságokkal felruházott számok a puszta véletlen folytán bukkanjanak fel újra és újra az összetett számok tengerében (az összetett számok a nem prímszámok, amelyeknek tehát kettőnél több osztójuk van, és végső soron felbonthatók prímtényezők szorzatára). Mindeddig azonban nem ismert olyan képlet, amely garantálná, hogy eredményül egy tetszőleges prímszámot ad, magyarul az újabb, immár szinte elképzelhetetlenül nagy prímek megtalálása rendkívül hosszadalmas művelet, az elvégzéséhez szükséges időtartam pedig leginkább a szerencse függvénye.

Jonathan Pace, a FedEx csomagküldő cégnél dolgozó villamosmérnök mostani találatában is a türelem játszotta a főszerepet. Ő (pontosabban komputere) tizennégy éve folyamatosan keresi a prímeket, és most (karácsony másnapján) járt szerencsével először. Egy több ezer önkéntest foglalkoztató internetes mozgalomhoz, a nagy internetes Mersenne-prím-kereséshez (Great Internet Mersenne Prime Search, GIMPS) csatlakozott saját számítógépének gépidejét felajánlva a közösségnek. Bárki követheti példáját, ha a mersenne.org/download címről letölti a kereséshez szükséges programot, majd vár türelemmel.

A GIMPS, ahogy neve is utal rá, nem is akármilyen prímszámot, hanem a még ritkább, úgynevezett Mersenne-prímet keresi. E szám a XVI–XVII. század fordulóján élő francia matematikus szerzetesről, Marin Mersenne-ről kapta a nevét, aki pályafutása során sokat foglalkozott a prímszámokkal, és nagyban hozzájárult a számelmélet fejlődéséhez. Sok korai matematikus úgy sejtette – magyarázza a Tennessee-i Egyetem honlapja –, hogy 2^n–1 kifejezéssel felírható számok minden prím n-re prímszámokat eredményeznek. Például 2^2–1=3, 2^3–1=7 és így tovább. Aztán kiderült, hogy nem, mivel a XVI. században Hudalricus Regius kimutatta, hogy a 2^11–1, amely 2047-tel egyenlő, nem prímszám, hanem a 23 és a 89 szorzata.

A következő években több hasonló képlettel felírható számról kiderült, hogy összetett, mígnem Marin Mersenne barát 1644-es Cogitata Physica-Mathematica könyvében kijelentette, hogy a 2^n–1 akkor ad prím számot, ha n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 vagy 257. Végül csak 1947-re – Mersenne munkája után 303 évvel – sikerült megvizsgálni az összes 258-nál kisebb számot, így a helyes lista szerint a 2^n–1 akkor prím, ha n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 vagy 127. Mersenne-nek tehát nem volt tökéletesen igaza, neve mégis rajtaragadt a 2^n–1 alakú prímszámokon.

Eddig mindössze ötven Mersenne-prímet találtak, az utolsó 16-ot a GIMPS önkéntesei. A mostani legnagyobbat bárki kiszámolhatja akár fejben is, mindössze 77 232 917-szer kell összeszorozni a kettőt önmagával, majd kivonni az eredményből 1-et (2^77 232 917–1). A szám a maga 23 249 425 számjegyével majdnem egymillió számjeggyel hosszabb, mint az előző rekorder.

A szám prím mivoltának bizonyítása hatnapnyi megállás nélküli kalkulációt igényelt Pace számítógépétől. Ezután négy önkéntes négyféle számítógépes programmal négy különféle komputeren ellenőrizte, hogy tényleg prímről van-e szó. Amikor megbizonyosodtak róla, a GIMPS kifizette az 51 éves Pace-nek a sikeres prímvadászoknak felajánlott, 3000 dolláros pénzjutalmat. Nem biztos, hogy a vagyonnak azért nem nevezhető díj fedezte a 14 évi villanyszámlát és a számítógépek amortizációjának költségét.

De persze az önkéntesek nem is a pénzért csinálják (bár az első 100 millió számjegy hosszúságú prímért már 150 ezer dollár lenne a jutalom), sokkal inkább a dicsőségért. Sőt Pace úgy érzi, hogy ezzel a hobbival a közjót is szolgálják, az amerikai közszolgálati National Public Radiónak adott indoklásában pedig felvillantja a nagy prímszámok felfedezésének tényleges hasznát is: „Ha majd egyszer tényleg kifejlesztik a kvantumszámítógépeket, az összes jelenlegi titkosítást milliszekundumok alatt fogják feltörni. Így szükség lesz a hihetetlenül nagy prímszámokra, és én ezt a prímszámot hagyhatom magam után örökül.”

Tehát a prímszámok a számítógépes titkosításban játsszák a legfontosabb szerepet. Sok kódoló algoritmus akkor engedi „feltörni” a titkosított adatokat, ha az illető megadja egy eszméletlenül nagy szám prímtényezőit. Ezek megtalálása elméletben nem bonyolult feladat (hiszen csak rengeteg, nála kisebb számmal kell elosztani, hogy az eredmény egész számot ad-e), de a mai komputerekkel sokszor millió évekre van hozzá szükség. Így az ezeken alapuló titkosítások ma még gyakorlatilag feltörhetetlenek. De ahogy fejlődik a számítástechnika, és gyorsulnak a számítógépek, előbb-utóbb minden titkosítás elavul. A nagy prímszámok ezt a folyamatot lassíthatják némileg.