GIMPS

A GIMPS (Great Internet Mersenne Prime Search) egy nagyszabású önkéntes számítástechnikai projekt Mersenne prímszámok keresésére .

A projekt céljai és módszerei

Annak meghatározása , hogy egy adott szám prím -e, általában nem olyan triviális feladat. Csak 2002- ben derült ki, hogy polinomiálisan megoldható. A javasolt (és elméletileg szigorúan indokolt) determinisztikus algoritmus azonban nagy, bár polinomiális összetettsége miatt gyakorlatilag alkalmatlan. Ezért a nyilvános kulcsú kriptográfiában , ahol prímszámokat használnak a sorrendben , az elsődlegességet továbbra is hatékony valószínűségi tesztek , például a Miller-Rabin teszt segítségével határozzák meg . Ha a gyakorlat megelégszik azokkal a számokkal, amelyek prímszámok közeli valószínűséggel , akkor az elmélet nem fogadja el az ilyen számokat: ha egy számot prímnek mondunk, ezt szigorúan be kell bizonyítani. Ezt a különbséget hangsúlyozza az algoritmusok valószínűségi és determinisztikus felosztása.

Ha megkérdezed magadtól, hogy mi az emberiség által ismert legnagyobb prímszám [1] , akkor a válasz valamilyen Mersenne-prímszám lesz . A Mersenne-számok alakja . Vegye figyelembe, hogy egy szám egyszerűsége magában foglalja a szám egyszerűségét is ; különben a for és a szám nem lesz egyszerű, tekintettel az oszthatóságra (as, sőt, -vel ).

Ahogy a neve is sugallja, a GIMPS projekt célja új Mersenne prímszámok felkutatása. Az eddig ismert legnagyobb prímszámot a GIMPS projekt találta 2018. december 7-én, és 24 862 048 tizedesjegyből áll. Sőt, 15 korábbi rekordot is felállítottak a GIMPS tagjai. Az ok az egyszerűségük hatékony (determinisztikus) kritériumának meglétében rejlik, amely Luc-Lemaire nevet viseli . A Mersenne-prímek kereséséhez a GIMPS-kiszolgáló egyszerű "kitevőket" oszt ki a kliensek között, hogy a Luc-Lehmer teszttel teszteljék a szám elsődlegességét.

2022 júliusáig 51 Mersenne-prím ismert, ezek közül az első 48-nak a sorozatszáma megbízhatóan ismert. A három legnagyobb ismert Mersenne-prím sorszámát még nem állapították meg megbízhatóan (közöttük más, még fel nem fedezett Mersenne-prímek is lehetnek). [2]

Gyakorlati jelentősége

A Mersenne - prímek folyamatosan tartják a rekordot , mint a legnagyobb ismert prímszámok.

Ezenkívül a Mersenne-prímek fontos szerepet játszanak néhány számelméleti problémában . Például Eukleidész felfedezte, hogy ha egy szám prím, akkor a szám tökéletes , azaz egyenlő a saját osztóinak összegével (példák ilyen számokra: 6=1+2+3, 28=1+2+4 +7+14, 496=1+ 2+4+8+16+31+62+124+248, majd Euler bebizonyította, hogy minden páros tökéletes számnak a jelzett alakja van (a páratlan tökéletes szám létezésének kérdése még nyitva ).

A Mersenne-prímek számának és aszimptotikájának végtelenségének kérdése nyitva marad . A talált Mersenne-prímek kiindulópontként szolgálhatnak a Mersenne-prímek viselkedésére vonatkozó hipotézisek felállításához és teszteléséhez.

A gyakorlatban a Mersenne-prímeket nagy periódusú pszeudovéletlenszám-generátorok készítésére használják (lásd Mersenne-örvény ).

Pénzdíjak

A GIMPS 100 000 dolláros pénzdíjat nyert [3] , mert több mint 10 millió tizedesjegyből álló prímszámot talált, és hasonló, 150 000 és 250 000 dolláros díjakat szándékozik elnyerni, amelyeket az Electronic Frontier Foundation ígér [4] azért, hogy több mint prímszámot találjon. 100 millió és 1 milliárd tizedesjegy. A díj összegéből a tervek szerint a korábbi Mersenne-prímek "felfedezőinek", szoftver- és új, hatékonyabb keresőalgoritmusok szerzőinek (ha találnak ilyen algoritmusokat) kifizetéseket terveznek.

A 2008 augusztusában talált szám 12 978 189 tizedesjegyet tartalmaz, amivel a GIMPS 100 000 dolláros díjat kapott. A következő, 150 000 dolláros nyeremény átvételéhez azonban több mint 100 millió tizedesjegyből álló elsőbbséget kell ellenőriznie, amelyek mindegyikéhez a számítástechnika és az algoritmus technológia jelenlegi fejlődése mellett több mint három évre lesz szüksége.

Versenyképes hatás

A GIMPS projekt minden nap több száz közreműködőtől kapja meg a számítások eredményeit. A projekt mindegyikre vonatkozóan statisztikát vezet, közzéteszi és rendszeresen frissíti a teljesítményt és a teljesítményértékeléseket. A versenyhatás fokozása érdekében a projektben megvalósult a résztvevők csapatokba tömörítésének lehetősége. Ebben az esetben a résztvevő eredményeit nemcsak neki, hanem csapatának is jóváírják. Ami az egyéni résztvevőket illeti, a projekt karbantartja és frissíti a csapatok értékelését.

A csapatokat általában a résztvevők tartózkodási helye (ország vagy város), szervezethez (oktatási intézményhez vagy céghez) való tartozásuk alapján alakítják ki, vagy egyszerűen csak egy adott online közösség támogatására való törekvésből.

Összesen több mint 1000 csapat vesz részt a projektben. Túlnyomó többségük kicsi, egy vagy több résztvevőből áll, sok már régóta nem aktív. A legnagyobb csapatok több tucat/száz résztvevőt foglalnak magukban, és gyakran nagy számítási teljesítmény tulajdonosai: néhány személyi számítógéptől egy „szponzorált” cég vagy egyetem számítógépes berendezéseinek teljes flottájáig.

Gyakran komoly küzdelem zajlik a csapatértékelések minden soráért. Egyes csapatok céltudatosan koordinálják tagjaik tevékenységét annak érdekében, hogy áttörést érjenek el a számítástechnika tervezett formájában, és a lehető leggyorsabban magasabb pozícióba kerüljenek. Általánosságban elmondható, hogy a csapatok TOP-10-es besorolása viszonylag stabil, meglepetéseket elsősorban az új résztvevők okoznak, akik váratlanul lépnek be a játékba egyik vagy másik csapat számára. Éppen ezért a csapatok mindig örömmel fogadják az új résztvevőket, a régiek pedig igyekeznek lehetőség szerint segíteni a hardver és szoftver beállításokban, tanácsot adni a legérdekesebb számítási módok kiválasztásában.

A siker valószínűsége

A heurisztikus becslések azt mutatják, hogy van még négy ismeretlen Mersenne-prím, amelyek kevesebb, mint 100 millió tizedesjegyből állnak, és közülük a legközelebbi körülbelül 26 millió számjegyből állhat [5] . Ezek lehetséges eloszlásáról , valamint a megtalálásukhoz várható munkaerőköltségről a projekt statisztika oldalán tájékozódhat. [6]

Hardver tesztelés

A GIMPS kliensprogram intenzív számításokat végez, folyamatosan figyelve azok pontosságát. Ezért sokan kiváló eszköznek tartják a számítógépes hardver stabilitásának tesztelésére . A csúcsterhelések és a szigorú vezérlés megkönnyíti a memóriával, gyorsítótárral, adatbusszal, a processzor túlhúzásával és túlmelegedésével stb. kapcsolatos problémák azonosítását. A tesztelési eljárás megkönnyítése érdekében a GIMPS kliens lehetőséget biztosít a „stressz teszt” módban történő munkavégzésre, amikor az ismert Mersenne-prímekre számításokat végeznek és a számítási eredményeket összehasonlítják a várttal.

Támogatott operációs rendszerek

A GIMPS projektszoftver kliens része [7] a következő operációs rendszerekhez érhető el :

• Microsoft Windows 7/Vista/XP/2008/2003/2000/NT/Me/98/95. A Windows 7/Vista/XP/2008 64 bites verzióihoz is létezik egy verzió .
• Mac OS X
• GNU/Linux (64 bites és 32 bites verziók)
• FreeBSD (64 bites és 32 bites verziók)

Jegyzetek

1. ↑ The Largest Known Primes archiválva 2008. november 22-én a Wayback Machine -nél 
2. ↑ GIMPS: Az ismert Mersenne -prímszámok listája archiválva 2016. március 15-én a Wayback Machine -nél 
3. ↑ Rekord 12 millió számjegyű prímszám nettó 100 000 dolláros díj archiválva 2011. augusztus 5. a Wayback Machine -nél 
4. ↑ EFF Cooperative Computing Awards archiválva : 2008. november 9. a Wayback Machine -nél 
5. ↑ Hol van a következő Mersenne-fő? Archiválva : 2021. március 9. a Wayback Machine -nél 
6. ↑ PrimeNet tevékenységi összefoglaló archiválva 2021. január 12-én a Wayback Machine -nél 
7. ↑ GIMPS kliens letöltése Archivált 2013. október 18. a Wayback Machine -nél 

Linkek

• mersenne.org ​(  eng.) - A GIMPS hivatalos webhelye (eng.)
• GIMPS eszközök és fejlett  statisztikák
•  GIMPS hivatalos fórum
• A GIMPS projektben résztvevők értékelése  (eng.)
• A csapatok értékelése a GIMPS projektben  (eng.)