Největší známé prvočíslo má 17 milionů číslic
7. 2. 2013 | Jindřich Zechmeister
Nekonečný proces hledání největšího prvočísla pokračuje. Nejnovějším největším prvočíslem je číslo 257885161-1 (17 425 170 číslic). V našem článku se krom jiného dozvíte, jak prvočísla souvisí s kryptografií a k čemu jsou dobrá.
Nekonečný proces hledání největšího prvočísla pokračuje. Nejnovějším největším prvočíslem je číslo 257885161-1 (17 425 170 číslic).
Začátek tohoto čísla můžete vidět na obrázku níže, dále pokračuje 17 miliony číslic. Chceme-li být matematicky přesní, musíme uvést, že se jedná o Mersennovo prvočíslo, které je o jedna menší než celočíselná mocnina dvojky.
Začátek největšího známého prvočísla. Zdroj: www.cbc.ca
Hledáním velkých prvočísel se matematicky zabývají již stovky let. Od poloviny devadesátých let se pro tento účel používá specializovaný software GIMPS. Na nové největší prvočíslo se čekalo téměř 4 roky. Ještě v roce 1989 jsme znali největší prvočíslo pouze o 65087 číslicích, ale v roce 1876 bylo největším prvočíslem číslo dokonce jen s 39 číslicemi. Historické zajímavosti o průběhu poznání největšího prvočísla naleznete v článku Largest known prime number na Wikipedii.
Co je to přesně prvočíslo?
Prvočíslo je přirozené číslo, které je beze zbytku dělitelné právě dvěma různými přirozenými čísly, a to číslem jedna a sebou samým (tedy 1 není prvočíslo). Přirozená čísla různá od jedné, která nejsou prvočísla, se nazývají složená čísla (Zdroj: Wikipedia). Ze školy známe malá prvočísla jako 2, 3, 5, 7, 11, 13 a další. Vědci se však za pomoci superpočítačů a distribuovaných výpočtů snaží posunout limity poznání a najít co největší prvočíslo. Tento proces je však nekonečný.
Jaký má tento výzkum význam?
Prvočísla mají velice důležitou úlohu v asymetrické kryptografii a jdou například základem šifrovacího algoritmu RSA. S tímto algoritmem se setkáváte denně při použití SSL protokolu na internetu, nebo při použití digitálního podpisu. Reálné využití však vysoká prvočísla milionech číslic zatím nemají.
RSA je první šifrovací algoritmus použitelný pro šifrování i podepisování. Bezpečnost RSA je postavena na předpokladu, že rozložit velké číslo na součin prvočísel (faktorizace) je velmi obtížná úloha. Z čísla n = pq je tedy v rozumném čase prakticky nemožné zjistit činitele p a q, neboť není znám žádný algoritmus faktorizace, který by pracoval v polynomiálním čase vůči velikosti binárního zápisu čísla n. Naproti tomu násobení dvou velkých čísel je elementární úloha (Zdroj: Wikipedia).
Chcete se také přidat k výzkumu?
Díky principu fungování ditribuovaných výpočtů se i vy můžete se svým počítačem stát součástí vědeckého výzkumu. Projekt distribuovaného výpočtu "rozdává" pracovní úlohy svým klientům (vy a váš počítač), které je zpracují, a vypočítaná data odešlou zpět. Takto je možné získat značnou výpočetní kapacitu zdarma. Místo superpočítačů úlohy počítají počítače dobrovolníků.
Mezi projekty zabývající se kryptografií a konkrétně hledáním prvočísel patří PrimeGrid (momentálně neaktivní). Další projekty související s kryptografií jsou Enigma@Home (rozluštění zpráv Enigma z roku 1942) a DistrRTgen (hledání nástrojů pro zjištění slabých hashů).
Program pro distribuované výpočty BOINC a "centrála" distribuovaných výpočtů se nachází na stránkách univerzity Berkeley.
