GIMPS

GIMPS

Prime95 běžící ve Wine .
Plošina své
Velikost stahování softwaru 4 MB
Velikost načtených dat úlohy <1 kB
Množství odeslaných dat úlohy <1 kB
Místo na disku 27 MB
Využité množství paměti 2,5 MB (TF),
45 MB (PM1-1),
>350 MB (PM1-2), 60 MB
( LL )
GUI ano ( pouze Windows a Mac OS X )
Průměrná doba výpočtu úkolu 20 minut. - 1 den (TF),
5 dní (PM1),
>2 měsíce (LL)
Uzávěrka Ne
Schopnost používat GPU Ano

GIMPS (Great Internet Mersenne Prime Search) je rozsáhlý dobrovolný počítačový projekt pro vyhledávání Mersennových prvočísel .

Cíle a metody projektu

Určit , zda je dané číslo prvočíslo , obecně není tak triviální úkol. Až v roce 2002 se ukázalo , že je polynomiálně řešitelný. Navržený (a přísně teoreticky zdůvodněný) deterministický algoritmus je však prakticky nevhodný pro svou velkou, byť polynomiální složitost. Proto v kryptografii s veřejným klíčem , kde se používají prvočísla řádu , se primálnost stále určuje pomocí účinných pravděpodobnostních testů , jako je Miller-Rabinův test . Jestliže se praxe spokojí s čísly, která jsou prvočísla s pravděpodobností blízkou , pak teorie taková čísla nepřijímá: jestliže se o čísle říká, že je prvočíslo, musí to být přísně dokázáno. Tento rozdíl je zdůrazněn v rozdělení algoritmů na pravděpodobnostní a deterministické.

Pokud se sami sebe zeptáte, jaké je největší prvočíslo [1] , které lidstvo zná, pak odpovědí bude nějaké Mersennovo prvočíslo . Mersennova čísla mají tvar . Všimněte si, že jednoduchost čísla implikuje jednoduchost ; v opačném případě pro a číslo nebude jednoduché z hlediska dělitelnosti (jako ve skutečnosti ).

Jak název napovídá, cílem projektu GIMPS je najít nová Mersennova prvočísla. Dosud největší známé prvočíslo našel projekt GIMPS 7. prosince 2018 a skládá se z 24 862 048 desetinných číslic. Členové GIMPS navíc vytvořili 15 předchozích rekordů. Důvodem je přítomnost efektivního (deterministického) kritéria pro jejich jednoduchost, které nese jméno Luc-Lemaire . Pro hledání Mersenneových prvočísel distribuuje server GIMPS klientům jednoduché „exponenty“, aby otestovali prvočíslost pomocí Luc-Lehmerova testu.

K červenci 2022 je známo 51 Mersennových prvočísel, přičemž sériová čísla prvních 48 z nich jsou spolehlivě známa. Pořadová čísla tří největších známých Mersennových prvočísel nebyla dosud spolehlivě stanovena (mezi nimi mohou být i jiná, dosud neobjevená Mersennova prvočísla). [2]

Praktický význam

Mersennova prvočísla trvale drží rekord jako největší známá prvočísla.

Navíc, Mersenne připraví důležitou roli v některých problémech v teorii čísel . Například Euklides objevil, že pokud je číslo prvočíslo, pak je číslo dokonalé , to znamená, že se rovná součtu svých vlastních dělitelů (příklady takových čísel: 6=1+2+3, 28=1+2+4 +7+14, 496=1+ 2+4+8+16+31+62+124+248 a Euler následně dokázal, že všechna sudá dokonalá čísla mají uvedený tvar (otázka existence lichého dokonalého čísla je stále otevřené ).

Otázka nekonečnosti počtu Mersennových prvočísel a jejich asymptotiky zůstává otevřená . Nalezená Mersennova prvočísla mohou sloužit jako výchozí bod pro předkládání a testování hypotéz o chování Mersennových prvočísel.

V praxi se Mersennova prvočísla používají ke konstrukci generátorů pseudonáhodných čísel s velkými periodami (viz Mersennův vír ).

Peněžité ceny

GIMPS vyhrál [3] peněžní odměnu 100 000 $ za nalezení prvočísla s více než 10 miliony desetinných číslic a má v úmyslu vyhrát podobné ceny 150 000 a 250 000 $ slíbené [4] od Electronic Frontier Foundation za nalezení prvočísel od více než 100 milionů a 1 miliarda desetinných číslic. Z výše této ceny je plánováno vyplácení všech „objevitelů“ předchozích Mersennových prvočísel, autorů softwaru a autorů nových, efektivnějších vyhledávacích algoritmů (pokud takové algoritmy najdou).

Bylo nalezeno v srpnu 2008 a obsahuje 12 978 189 desetinných číslic, což GIMPS vyneslo ocenění 100 000 $. Chcete-li však získat další cenu 150 000 $, budete muset zkontrolovat, zda je primálnost více než 100 milionů desetinných číslic, z nichž každá bude při současném vývoji výpočetní a algoritmické technologie vyžadovat více než tři roky.

Konkurenční efekt

Každý den dostává projekt GIMPS výsledky výpočtů od stovek přispěvatelů. U každého z nich projekt vede statistiky, publikuje a pravidelně aktualizuje hodnocení výkonu a výkonu. Pro posílení konkurenčního efektu v projektu byla implementována možnost spojování účastníků do týmů. V tomto případě se výsledky účastníka připisují nejen jemu, ale i jeho týmu. Co se týče jednotlivých účastníků, projekt udržuje a aktualizuje hodnocení týmů.

Týmy jsou obvykle tvořeny podle místa, kde se účastníci nacházejí (země nebo město), podle příslušnosti k organizaci (vzdělávací instituci nebo společnosti) nebo jednoduše z touhy podpořit určitou online komunitu.

Celkem se projektu účastní více než 1000 týmů. Naprostá většina z nich jsou malé, skládají se z jednoho nebo více účastníků, mnozí již dávno přestali být aktivní. Mezi největší týmy patří desítky/stovky účastníků a často majitelé velkého výpočetního výkonu: od několika osobních počítačů až po celou flotilu počítačového vybavení „sponzorované“ společnosti nebo univerzity.

Často se o každou linii v hodnocení týmů odehrává vážný boj. Některé týmy cíleně koordinují počínání svých členů, aby prorazily v zamýšlené formě počítání a co nejrychleji se dostaly na vyšší pozice. Celkově je týmové TOP-10 hodnocení poměrně stabilní, překvapení přinášejí především noví účastníci, kteří nečekaně vstupují do hry za ten či onen tým. Týmy proto vždy rády přivítají nové účastníky a staromilci se jim snaží co nejvíce pomoci s nastavením hardwaru a softwaru a poradit s výběrem nejzajímavějších typů výpočtů.

Pravděpodobnost úspěchu

Heuristické odhady ukazují, že existují ještě čtyři neznámá Mersennova prvočísla, sestávající z méně než 100 milionů desetinných číslic, a nejbližší z nich může obsahovat asi 26 milionů číslic [5] . Podrobné informace o jejich možném rozložení a také o předpokládaných mzdových nákladech na jejich vyhledání lze získat na stránce statistik projektu. [6]

Testování hardwaru

Klientský program GIMPS provádí intenzivní výpočty a neustále sleduje jejich přesnost. Proto jej mnozí považují za vynikající nástroj pro testování stability počítačového hardwaru . Špičkové zatížení a přísná kontrola usnadňují identifikaci problémů s pamětí, mezipamětí, datovou sběrnicí, přetaktováním a přehříváním procesoru atd. Pro usnadnění testovací procedury poskytuje klient GIMPS možnost pracovat v režimu „zátěžového testování“, kdy se provádějí výpočty pro známá Mersennova prvočísla a výsledky výpočtu jsou porovnávány s očekávanými.

Podporované operační systémy

Klientská část softwaru projektu GIMPS je dostupná [7] pro následující operační systémy :

Poznámky

  1. ↑ Největší známá prvočísla archivována 22. listopadu 2008 na Wayback Machine 
  2. ↑ GIMPS: Seznam známých Mersennových prvočísel archivován 15. března 2016 na Wayback Machine 
  3. ↑ Rekordní 12milionové prvočíslo čisté ceny 100 000 $ Archivováno 5. srpna 2011 na Wayback Machine 
  4. ↑ EFF Cooperative Computing Awards Archivováno 9. listopadu 2008 na Wayback Machine 
  5. ↑ Kde je další Mersennovo prvočíslo? Archivováno 9. března 2021 na Wayback Machine 
  6. ↑ Souhrn aktivit PrimeNet Archivováno 12. ledna 2021 na Wayback Machine 
  7. ↑ Stáhnout klienta GIMPS Archivováno 18. října 2013 na Wayback Machine 

Odkazy