Největší známá prvočísla
Dnes největší známé prvočíslo se skládá z více než 41 milionů dekadických číslic. Jedná se o 2136 279 841 − 1, což znamená, že v binárním tvaru je toto prvočíslo tvořeno 136 279 841 jedničkami. Čísla podobných rozměrů jsou dnes již výhradně hledána pomocí distribuovaného výpočtu. Poslední prvočíslo bylo objeveno po šesti letech od předchozího takového objevu.
Distribuovaný projekt, který objevil již 18 největších prvočísel (včetně toho posledního), se nazývá Great Internet Mersenne Prime Search (GIMPS) a funguje již 28 let. Dnes má výkon téměř 10 000 TFLOP/s. Zabývá se hledáním tzv. Mersennových prvočísel, což jsou prvočísla čísla ve tvaru 2p − 1, kde p je také prvočíslo. Díky svým vlastnostem mají v matematice a informatice speciální postavení (například generátor pseudonáhodných čísel Mersenne twister).
Mersennových prvočísel je dosud známo pouze 52 (včetně toho nově nalezeného). Prvočíslo bylo nalezeno pomocí Fermatova testu prvočíselnosti programem Gpuowl na GPU Nvidia A100. (Zajímavostí je, že na rozdíl od předchozích takto objevených prvočísel nebylo objeveno pomocí CPU, ale pomocí GPU).
První čtyři Mersennova prvočísla (3, 7, 31, 127) byla známa již matematikům starověkého Řecka. Další čtyři byla objevena v průběhu staletí metodou zkusmého dělení. Poslední z této čtveřice, 231 − 1 neboli 2 147 483 647 objevil v roce 1772 švýcarský matematik a fyzik Leonhard Euler. Další čtyři byla už objevena pomocí Lucasových řad. Největší z nich, 2127 − 1, objevil v roce 1876 (po 19 letech ručního výpočtu) francouzský matematik Édouard Lucas.
Když hledají počítače
Od roku 1952 již objevují nová Mersennova prvočísla jen počítače. V roce 1996 bylo první takové prvočíslo objeveno v rámci internetového projektu GIMPS (tehdy na 90 MHz počítači s procesorem Pentium). Od tohoto roku až dodnes byla všechna nově nalezená Mersennova prvočísla objevena právě v rámci tohoto projektu. Právě to poslední z nich se datuje na 12. října 2024 (s oznámením objevu se čekalo do 21. října 2024).
Kdybychom chtěli nově nalezené prvočíslo vyjádřit v desítkové soustavě, vypadalo by nějak takhle: 881694327…486871551, přičemž na místě výpustky bylo vynecháno něco přes 41 milionů číslic. Přesně se jeho krásou můžete pokochat po rozbalení archivu ZIP. Nicméně číslo jako takové nemá moc praktických využití, a to zejména kvůli své velikosti. Čísla podobné magnitudy budou v paměti počítače zabírat zhruba 16 megabajtů (srovnejte například s běžně používaným 4bajtovým datovým typem int v jazyce C).
Mersennova prvočísla byla dříve v rámci projektu GIMPS hledána pomocí Lucasova-Lehmerova testu prvočíselnosti (LL). Čísla 2p − 1, kde p je prvočíslo, se nazývají Mersennova čísla. Lucasův-Lehmerův test dokáže, zdali je Mersennovo číslo prvočíslem nebo ne (ale neposkytne faktor, pokud je testované číslo složené). Lucasův-Lehmerův test lze popsat velmi jednoduše. Iteruje funkci xn = ((xn-1)2 − 2) modulo Mp, kde x0 = 4 a Mp je testované Mersennovo číslo. Když je po p − 2 iteracích výsledek 0, pak Mp je prvočíslo, jinak je to číslo složené.
Dnes se již v rámci projektu GIMPS používá k testování Fermatův test prvočíselnosti (PRP). Jedná se ale pouze o pravděpodobnostní test, který může dokázat, že testované číslo je složené, ale nedokáže, že se jedná o prvočíslo (pouze určí, že se jedná pravděpodobně o prvočíslo). Fermatův test je velmi podobný Lucasovu-Lehmerovu testu. Test iteruje funkci xn = xn-12 modulo Mp, kde x0 = 3 a Mp je opět testované Mersennovo číslo. Když je po p iteracích výsledek 9, pak je Mp pravděpodobně prvočíslo, jinak se jedná o číslo složené. Samozřejmě po Fermatově testu je pro potvrzení kladného výsledku třeba spustit Lucasův-Lehmerův test.
Můžete se přidat
Pokud byste se chtěli zapojit do projektu GIMPS a nalézt další největší prvočíslo (je za to odměna 3 000 USD), navštivte stránku mersenne.org. Zaregistrujte se a stáhněte si nejnovější verzi Prime95 pro svou platformu. Stažený archiv rozbalte. V Linuxu se program ke spuštení jmenuje mprime. Spouštějte pomocí ./mprime -d nejlépe ve screenu nebo tmuxu. Při prvním spuštění se program nakonfiguruje. Program běží na CPU a jednoho prvočíselného kandidáta testuje typicky několik dnů (záleží na výkonu CPU). Své výsledky uvidíte po přihlášení na webových stránkách.
Zbývá otázka, co vám zapojení do projektu přinese. V první řadě jsou to o něco vyšší účty za elektřinu. Na druhou stranu tu máme několik výhod. V první řadě dobře otestujete svůj hardware (pomůže s detekcí hardwarových problémů jako je nedostačující chlazení nebo problémy s CPU). Zkuste si pustit na pár hodin LL test, který je na chyby náchylný. Pokud dojte k chybě (nesouhlasí kontrolní součet), zpráva se vám ihned vypíše do konzole.
Dalším důvodem pro může být finanční odměna. Za objevení prvočísla pod 100 milionů číslic je odměna 3 000 USD. Pokud se vám podaří tuto hranici překonat, odměna činí 50 000 USD. Dalším důvodem pro objevení prvočísla je zařazení vašeho jména po boku takových jmen jako Mersenne, Fermat, Lucas. Pro inspiraci se podívejte na mersenne.org/primes.
ČLÁNKY DO MAILU