Objeveno nové nejvyšší prvočíslo. Má skoro 25 milionů číslic

7
kalkulačka číslo
Ilustrační foto (zdroj: fancycrave1 / Pixabay)

Necelý rok trvalo překonat předchozí rekordní prvočíslo s 23 miliony číslic. Sedmého prosince objevil Patrick Laroche ještě vyšší. Má zápis M82589933, je tedy rovné 2^82 589 933 − 1. Kdybyste jej rozepsali, bude mít 24 862 048 číslic. Kdybyste se na něj chtěli podívat, najdete jej v tomto ZIPu o velikosti 11 MB.

Laroche je 35letý ajťák z Floridy, jeden z tisíců dobrovolníků zapojených do projektu Great Internet Mersenne Prime Search (GIMPS). Počítač s procesorem Intel Core i5-4590T a programem Prime95 se potil 12 dní, než číslo objevil. Následná ověření třetími stranami pomocí výpočetních karet nebo cloudových serverů již trvalo v řádu desítek hodin.

Aktuální nejvyšší prvočíslo má 24,8 milionu číslic
Aktuální nejvyšší prvočíslo má 24,8 milionu číslic

Cílem GIMPSu je hledat a potvrzovat nejvyšší Mersennova prvočísla. Ta jsou definována jako mocniny dvojky, od kterých odečtete jedničku. Ne všechny mocniny tomu odpovídají. U 2^2 − 1 = 3 nebo 2^3 − 1 = 7 to souhlasí, ale už 2^4 − 1 = 15 dojdeme ke složenému číslu. Prohlásit objevení nejvyššího prvočísla se proto neobejde bez zdlouhavého ověření, zdali číslo opravdu není beze zbytku dělitelné ničím jiným než jedničkou a sebou samým. Édouard Lucas v roce 1879, po 19 letech zkoumání potvrdil, že prvočíslem je 2^127 − 1. Mělo 39 číslic. Vyšší Mersennova prvočísla už na papíře nikdo nespočítal, postaraly se o to až počítače. Aktuálně existuje 51 známých „mersennů“.

TIP: Historie hledání prvočísel pomocí počítačů

K čemu tak vysoká prvočísla potřebujeme? Využívají se při generování pseudonáhodných čísel a hrají klíčovou úlohu v kryptografii. Pro šifrování dnes ale takto tolikaciferná čísla nepotřebujeme, takže výpočty jsou spíš otázkou prestiže a vidiny finanční odměny. Nadace GIMPS daruje každému dalšímu objeviteli Mersennova prvočísla 3000 až 5000 dolarů. Electronic Frontier Foundation pak věnuje 150 000 dolarů tomu, kdo objeví a ověří prvočíslo o 100 milionu číslic.

Objeveno nové nejvyšší prvočíslo. Má skoro 25 milionů číslic

Ohodnoťte tento článek!
4.6 (91.61%) 31 hlas/ů

7 KOMENTÁŘE

  1. „Prohlásit objevení nejvyššího prvočísla se proto neobejde bez zdlouhavého ověření, zdali číslo opravdu není beze zbytku dělitelné.“

    To se nemusí moc dlouho ověřovat… Každý by měl vědět, že každé přirozené číslo je beze zbytku dělitelné… Jedničkou a samo sebou…

    • Protože to deterministicky ověřit není vůbec sranda. Deterministické algoritmy mají velkou složitost a nedeterministické nemusí vždy fungovat na 100%. Nejjednodušší, ale časově nepoužitelné řešení, je zkoušet dané číslo dělit všemi prvočísly až do velikosti druhé odmocniny testovaného čísla. Spočítej si, kolik toho při testu čísla o délce 25 milionů číslic bude.
      Podívej se zde https://www.wikihow.cz/Jak-zjistit,-zda-je-%C4%8D%C3%ADslo-prvo%C4%8D%C3%ADslem nebo https://math.feld.cvut.cz/gollova/mkr/mkr9.pdf.

        • Já vím, jak se ověřuje prvočíselnost… Ale autor článku píše, že se ověřuje nikoliv prvočíselnost, ale „zdali číslo opravdu není beze zbytku dělitelné“. Narážím na formální nepřesnost takového tvrzení. Jednak dělitelnost je vždy „čeho“ a „čím“ a není definovaná sama osobě, druhak je potřeba ověřovat „nedělitelnost“ pouze jak bylo zmíněno prvočísly menšími nebo rovnými odmocnině z potvrzovaného čísla…

          Pokud by to bylo, jak píše autor článku, žádné prvočíslo by neexistovalo, protože každé přirozené číslo je dělitelné přinejmenším jedničkou a samo sebou (bez újmy na obecnosti i jednička, pro kterou jsou tato dvě čísla rovna…). Nic by se pak ověřovat nemuselo, triviálně by se řeklo, že číslo je dělitelné a konec.