Vědci vypočítali dosud nejvyšší prvočíslo. Má 22 mil. číslic a jeho ověření trvalo měsíc

22. 1. 2016

Sdílet

 Autor: Redakce

První prvočísla se počítala na papíru

Už na základní škole jste se o prvočíslech učili. Jsou to taková, která jsou beze zbytku dělitelná pouze jedničkou nebo sebou samým (kromě jedničky). Prvočísly jsou 2, 3, 5, 7, 11, 13… a tím největším ověřeným je aktuálně 274 207 281 − 1. Představit si jej můžete jako 22 338 618 číslic za sebou, je jich o pět milionů více než u předchozího rekordu z roku 2013. Zazipovaný textový soubor s kompletním zněním si můžete stáhnout odsud, má jen 10 MB.

Pomocí programu Prime95 se můžete zapojit do distribuovaných výpočtů i vy
Pomocí programu Prime95 se můžete zapojit do distribuovaných výpočtů i vy 

Jde o tzv. Mersennovo prvočíslo pojmenované podle francouzského matematika Marina Mesenna, který prvočísla studoval začátkem 17. století. „Jeho“ prvočísla jsou o jedničku menší než celočíselné mocniny dvojky. Do nástupu počítačů se vše počítalo ručně. Édouard Lucas v roce 1879, po 19 letech zkoumání potvrdil, že prvočíslem je 2127 − 1. Mělo 39 číslic. Vyšší už nikdo jiný nespočítal.

Počítače všechno změnily

To se změnilo až 30. ledna 1952. Raphael Robinson na elektronkovém počítači SWAC objevil Mersennovo prvočíslo s mocnitelem 521, mělo 157 číslic. Rekord ještě v tomtéž roce čtyřikrát navýšil až na mocnitel 2281 (687 číslic). Jednotlivci jej navyšovali ještě 17×, když přišel zlom v roce 1996.

Tehdy odstartoval projekt GIMPS (Great Internet Mersenne Prime Search) a s ním známý program Prime95. Prvočísla už neověřoval jediný fyzický počítač, ale virtuální superpočítač tvořený desítkami (a dnes již více než milionem) procesorů spřažených přes internet. Posledních 15 Merssenových prvočísel již má na svědomí GIMPS. Aktuálně objevené je v pořadí čtyřicáté deváté.

Prvočíslo objevil doktor Curtis Cooper pracující na University of Central Missouri. Právě jeho škola poskytuje největší výpočetní kapacitu pro distribuované výpočty v GIMPSu. Pro něj a jeho tým je to již čtvrté objevené Mersennovo prvočíslo, držel i poslední rekord.  Za objev dostal od nadace GIMPS 3000 dolarů. Ostatní, kteří přes distribuované výpočty ověřili všechna menší prvočísla, si zaslouží alespoň respekt.

" frameborder="0" height="360" width="640">

Vtipné je, že Cooperův počítač ono prvočíslo objevil už v 17. září 2015, ale kvůli chybě počítač neodeslal e-mail a doktor se o výsledku dozvěděl až po měsíci při rutinní kontrole databáze. Následovalo zdlouhavé ověřování. Na Cooperově počítači s procesorem Intel Core i7-4790 běžel výpočet nepřetržitě celý měsíc.

Aby mohl být výsledek schválen, museli jej nezávisle ověřit ještě na jiném softwaru i hardwaru. Andreas Hoglund a David Stanfill zapojili farmu grafik GeForce Titan a počítali 2,3 dne v programu CUDALucas. David Stanfill s grafikami Radeon Fury X a programu CILucas počítal 3,5 dne. Sergej Batalov pak pomocí programu MLucas počítal 3,5 dne na dvou 18jádrových serverech Amazon EC2 s procesory Intel Xeon.

Tatko vypadá největší prvočíslo, soubor má přes 220 000 řádků
Tatko vypadá největší prvočíslo, soubor má přes 220 000 řádků

Proč se prvočísly zabývat?

K čemu tak vysoká prvočísla potřebujeme? Vlastně k ničemu. Prvočísla se využívají při generování pseudonáhodných čísel, takže hrají klíčovou úlohu v kryptografii. Jenže pro šifrování nepotřebujeme tolikaciferná čísla. Výpočty jsou tak 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.

 

Výpočty přes zmíněný software Prime95 ale mají i praktický dopad. Tento software se používá coby benchmark pro testování rychlosti a stability počítačů. Zrovna nedávno byla díky němu objevena chyba v procesorech Intel Skylake. Více se o ní dočtete v článku Honzy Olšana.

ICTS24

Zajímavé odkazy:

Zdroj: Mersenne via BBC