Mersennovo prvočíslo nalezeno?

Na adrese ftp://entropi­a.com/gimps/pri­me4.txt je dostupné dosud největší známé prvočíslo 2^6 972 593-1. Toto prvočíslo je prvé známé megaprvočíslo, tedy prvočíslo, které má více jak milión cifer (přesně 2 098 960!), druhé největší známé prvočíslo 2^3 021 377-1 (třicáté sedmé Mersennovo prvočíslo) má „jen“ 909 526 cifer. Pro lepší představu o jeho velikosti uvedeme, že při tisku (bold 10) zabere cca 110 stránek A4. Při zápisu do řady, kde jedna číslice je široká 1 mm a mezery mezi číslicemi zanedbáme, by bylo toto číslo více jak 2 km dlouhé.

Zdá se, že rekord, který toto číslo drží od roku 1999, bude v nejbližší době překonán! Na Slashdotu bylo 14. 11. 2001 jedním z čtenářů oznámeno, že bylo pravděpodobně nalezeno 39. (třicáté deváté) Mersennovo prvočíslo. Očekává se, že Primenet, který hledání tohoto čísla organizoval, tuto zprávu přibližně do týdne oficiálně potvrdí (24. 11. 2001). (http://www.ut­m.edu/research/pri­mes/mersenne.shtml)

Jaký bude nový rekordman? Toto číslo bude mít více jak 3 500 000 cifer, stane se tedy dosud největším známým prvočíslem. Jeho velikost je pro odborníky tak trochu překvapením. Matematici totiž předpokládali, že 39. Mersennovo prvočíslo bude ještě výrazně větší a odhadovali, že by mohlo mít až 10 000 000 cifer.

Co jsou vlastně Mersennova prvočísla?

Mersennova prvočísla jsou prvočísla speciálního tvaru, a to M_n = 2ⁿ – 1. Aby číslo uvedeného tvaru mohlo být prvočíslo, musí být exponent n prvočíslem. Jedná se ovšem jen o podmínku nutnou.

Začátkem 17. století vyslovil francouzský matematik (a teolog) Marin MERSENNE (1588 – 1648) hypotézu, že pro n menší jak 258 jsou čísla tvaru M_n = 2ⁿ  – 1 prvočísly právě pro n = 1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257

Prvočísla tvaru M_n = 2ⁿ – 1 se v současné době na jeho počest nazývají Mersennova prvočísla.

Mersennova prvočísla se zapisují vzestupně do tabulky a je zvykem je označovat pořadovým číslem v této tabulce. Tabulka dosud nalezených Mersennových prvočísel je uvedena jako příloha k tomuto článku.

Vraťme se k Mersennově hypotéze. Hypotéza byla v následujících letech testována mnoha matematiky a postupně se podařilo odstranit chyby, které obsahovala.

V intervalu 1–257 byla vynechána celkem tři Mersennova prvočísla a naopak dvě z uvedených čísel jsou čísla složená:

• vynechána byla deváté, desáté a jedenácté Mersennovo prvočísla, tedy M₆₁ , M₈₉ a M₁₀₇ (přičemž pro n=61, M₆₁ =2⁶¹ – 1 byla prvočíselnost dokázána teprve v roce 1883)
• složenými čísly jsou naopak M₆₇ a M₂₅₇ (Číslo M₆₇ = 2⁶⁷  – 1 = 193707721*761­838257287 rozložil Cole roku 1903)

Důležitým kritériem, zda Mersennovo číslo je, nebo není prvočíslo, je Lucas (1870)-Lehmerův (1930) test. Síla tohoto testu je mimo jiné v tom, že jej lze snadno zrealizovat pomocí výpočetní techniky.

Lucas-Lehmerův test:

Nechť n je liché prvočíslo. Pak je M_n prvočíslem právě tehdy, když dělí číslo S(n-2), kde S(0)=4, S(k+1) = S(k)² – 2.

Podrobnosti (včetně vysvětlení použitého značení) naleznete např. na adrese http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/LucasLehmer­.html

Koncem roku 1998 bylo nalezeno celkem 37 Mersennových prvočísel. Na základě rozboru všech těchto prvočísel byla vytvořena hypotéza o jejich rozložení a byly experimentálně určeny parametry lineární funkce, která určuje závislost exponentu n Mersennova čísla na jeho pořadí v tabulce (tzv „lineární hypotéza“). Z této „lineární hypotézy“ se dalo očekávat, že třicáté osmé Mersennovo prvočíslo bude mít exponent přibližně roven 4,699,385. Při systematickém prohledávání vhodných kandidátů bylo v roce 1999 objeveno nové Mersennovo prvočíslo (v současné době označováno jako třicáté osmé), jenže jeho exponent je 6972593, což by bylo v dobré shodě pro třicáté deváté Mersennovo prvočíslo (předpověď z lineární hypotézy je: 6,935,171). Řada odborníků se tedy domnívala, že při prohledávání prostoru kandidátů na třicáté osmé Mersennovo prvočíslo se podařilo příslušnou hodnotu „přeskočit“. Na projektu se podílely stovky dobrovolníků, kteří hypotézu testovali na svých PC, a je tedy možné, že některý z dobrovolníků „selhal“. V roce 2000 a 2001 byl tento prostor znovu prohledáván. V každém případě poslední objevené Mersennovo prvočíslo bylo až dosud největším známým prvočíslem a stalo se prvým megaprvočíslem  – tedy prvočíslem, které má ve svém dekadickém zápisu více jak milión cifer.

Příloha 1: „Lineární hypotéza“ rozložení Mersennových prvočísel

e^G log₂ n – 1.462 With Respect to N, and the Line y = x
(G je Eulerova gamma funkce (0.5772156649…) a e je základ přirozeného logaritmu (2.718281828…))

Očekávané hodnoty exponentu n pro n-té Mersennovo prvočíslo, vypočtené podle „lineární hypotézy“

N exponent n v 2ⁿ-1
38 4,699,385
39 6,935,171
40 10,234,658
41 15,103,913
42 22,289,772
43 32,894,385
44 48,544,264
45 71,639,751
50 501,458,270

Pokud se potvrdí zpráva na Sladshotu a bylo nalezeno 39. Mersennovo prvočíslo, jehož velikost bude skutečně „jen“ 3 500 000 cifer, bude zde argument pro to, že lineární hypotéza prostě neplatí! Tím by se také dalo vysvětlit, proč již při hledání 38. Mersennova prvočísla nebylo s jeho očekávanou délkou vše úplně v pořádku. Prostě by se jen potvrdilo, že o rozložení prvočísel toho zatím víme málo a jedná se stále o jeden z otevřených problémů, patřících mezi krásné nerozřešené záhady matematiky.

Příloha 2: Tabulka všech dosud nalezených Mersennových prvočísel

* 1.6. 1999, Nayan Hajratwala, GIMPS the Great Internet Mersenne Prime Search

** http://www.ut­m.edu/research/pri­mes/mersenne.shtml

------------------------------------------

Adresy pro zvídavé zájemce:

Mersennova prvočísla – přehled: http://homepa­ges.go.com/~jo­ekorovin/Mersen­ne.html
Uloženo celé 38 Mersennovo prvočíslo ftp://entropi­a.com/gimps/pri­me4.txt
Lucas-Lehmer test: http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/LucasLehmer­.html
Caldwell, Chris K. „Mersenne Primes: History, Theorems and Lists.“ Prime Pages
(1999). Online. Internet. Accessed November 22, 1999. Available HTTP: http://www.ut­m.edu/research/pri­mes/mersenne.shtml Caldwell, Chris K. „The Largest Known Prime by Year: A Brief History.“ Prime Pages
(1999). Online. Internet. Accessed November 22, 1999. Available HTTP:
http://www.ut­m.edu/research/pri­mes/notes/by_y­ear.html
Caldwell, Chris K. „Where is the next larger Mersenne prime?“ Prime Pages (1999).
Online. Internet. Accessed November 22, 1999. Available HTTP:
http://www.ut­m.edu/research/pri­mes/notes/faq/Nex­tMersenne.html
Caldwell, Chris K. „Lucas-Lehmer Theorem.“ Prime Pages (1999). Online. Internet.
Accessed November 22, 1999. Available HTTP: http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/LucasLehmer­.html
Caldwell, Chris K. „Modular restrictions on Mersenne divisors.“ Prime Pages (1999).
Online. Internet. Accessed November 22, 1999. Available HTTP: http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/MerDiv.html
Caldwell, Chris K. „Prime-square Mersenne divisors are Wieferich.“ Prime Pages
(1999). Online. Internet.Accessed November 22, 1999. Available HTTP: http://www.ut­m.edu/research/pri­mes/notes/pro­ofs/SquareMer­Div.html
Kurowski, Scott. „Current Internet PrimeNet Server World Test Status.“ Entropia.com
(November 22, 1999). Online. Internet. Accessed November 22, 1999. Available HTTP: http://entropi­a.com/primenet
O’Connor, John J., and Robertson, Edmund F. „Prime numbers.“ The MacTutor History
of Mathematics Archive (December 1996). Online. Internet. Accessed
November 22, 1999. Available HTTP: http://www-history.mcs.st-andrews.ac.uk/his­tory/HistTopic­s/Prime_number­s.html
Williams, Hugh C. édouard Lucas and Primality Testing. New York: John Wiley & Sons, Inc., 1998.
Wiman, Lucas, et al. „The Mersenne Prime Mailing List FAQ.“ Mersenne FAQ (1999).
Online. Internet. Accessed November 22, 1999. Available HTTP: http://www.ta­sam.com/~lrwi­man/faq-mers
Woltman, George. „38th Mersenne Prime Discovered.“ Mersenne.org (June 30, 1999).
Online. Internet. Accessed November 22, 1999. Available HTTP: http://www.mer­senne.org/6972593­.htm
Woltman, George. „Mersenne Prime Search.“ Mersenne.org (October 4, 1999). Online.
Internet. Accessed November 22, 1999. Available HTTP: http://www.mer­senne.org/pri­me.htm