Původní článek:https://www.math.ucla.edu/~edson/prime/
V srpnu 2008 bylo na jednom z počítačů, které patří do Programu výpočetní techniky (PIC) katedry matematiky UCLA, objeveno nové číslo Mersenne Prime . Ukázalo se, že toto číslo je největší známé prvočíslo na světě a objev vyvolal velký zájem. Ve snaze ušetřit všem čas a energii jsem si řekl, že dám nějaké informace na web ve formátu FAQ. Vzhledem k tomu, že řada otázek, které jsem obdržel, pocházela od lidí s netechnickým vzděláním (včetně dětí), nejsou tyto často kladené otázky technického rázu. Musíte však vědět, co je prvočíslo.
Jsem však nucen nabídnout toto upozornění: i když pracuji na katedře matematiky, jsem systémový administrátor, nikoli matematik! Pokud hledáte seriózní informace o Mersenne Prime, odkazuji vás na vynikající webovou stránku Chrise Caldwella Mersenne Primes: History, Theorems and Lists. Mezi další zajímavé stránky patří Wolframova stránka Mersenne Prime a zábavná Mersenne Prime Digits and Names od Landona Curta Nolla.
A teď k otázkám!
Otázka: Co je tedy Mersenne Prime?
Odpověď: Stručně řečeno, existuje určitá podtřída prvočísel známých jako Mersennova prvočísla . Jsou pojmenovány po Marin Mersenne , matematik 17. století. V době psaní tohoto článku je známo méně než 50 Mersenne Primes.
Mersennova prvočísla mají všechna tvar 2 P -1, kde P je známé prvočíslo. První Mersennovo prvočíslo je 3, protože 2 2 -1 = 3. Všimněte si, že exponent P je prvočíslo, v tomto případě 2. Další Mersennovo prvočíslo je 7, protože 2 3 - 1 = 7, přičemž P je prvočíslo 3 . Následuje 31 (2 5 – 1), poté 127 (2 7 – 1), 8191 (2 13- 1) a 131071 (2 17 - 1).
Jak můžete vidět, po několika prvních se Mersenne Primes velmi rychle zvětší. Je zde pěkná tabulka známých Mersenne Primes, která poskytne určitou perspektivu.
Nejmenší z těchto čísel byla známa ve starověku, ale až v roce 1951 bylo objeveno pouze 12. Za posledních 50 let bylo pomocí počítačů odhaleno několik desítek dalších. Nejnověji objevené Mersenne Primes jsou neuvěřitelně velké, s miliony číslic. UCLA Mersenne Prime má délku přibližně 12,9 milionu číslic.
Všimněte si, že všechna Mersennova prvočísla jsou prvočísla, ale jen velmi málo prvočísel jsou Mersennova prvočísla.
Otázka: Co je UCLA Mersenne Prime? Proč je speciální?
Odpověď: UCLA Mersenne Prime je první objevené prvočíslo, které má více než 10 milionů číslic. Byl objeven na katedře matematiky UCLA 23. srpna 2008.
Všechny Mersenne Primery jsou speciální, protože jsou tak vzácné, ale tento si získal zvláštní pozornost, protože se kvalifikuje na cenu (viz níže).
Číslo UCLA Mersenne Prime je 2 43112609 - 1. Skutečné číslo má 12 978 189 číslic. Pokud jste tak nakloněni, dlouholetý výzkumník Mersenne Prime Landon Curt Noll zpřístupnil samotné číslo zde . Pokud jste opravdu, opravdu nakloněni, poskytuje zde také celé číslo v angličtině (všech 328 megabajtů).
Otázka: Je to první Mersenne Prime UCLA?
Odpověď: Ve skutečnosti je to osmý Mersenne Prime UCLA!
V roce 1952 našel profesor Raphael Robinson 5 nových Mersenne Primes pomocí UCLA's Standards Western Automatic Computer (SWAC) , jednoho z nejrychlejších počítačů své doby. Jednalo se o 13. až 17. objevené Mersenne Primery a každý měl stovky číslic. Robinsonovy Mersenne Primes byly první nalezené po 75 letech a první, které byly objeveny pomocí digitálního počítače.
V roce 1961 matematik UCLA Alexander Hurwitz objevil 19. a 20. Mersenne Primes na sálovém počítači IBM 7090 UCLA Computer Center . Každé z těchto čísel mělo více než 1200 číslic.
Nyní, o 47 let později, tradice UCLA hledání Mersenne Primes pokračuje!
Otázka: Kdo hledá Mersenne Primes? jak na to jdou?
Odpověď: Tisíce lidí používajících desítky tisíc počítačů se účastní Great Internet Mersenne Prime Search (GIMPS), organizovaného úsilí věnovaného hledání Mersenne Primes. Toto je jedno z mnoha probíhajících snah na poli distribuovaných výpočtů a pravděpodobně nejúspěšnější.
Hledání je velmi dobře organizované. Dobří lidé z Primenetu koordinují úsilí posledních 12 let a poskytují vynikající Prime95program zdarma pro každého, kdo jej chce provozovat. Sledují, která čísla byla testována, a poskytují komunitě GIMPS stálý proud nevyzkoušených kandidátských čísel. Účastníci GIMPS jsou seřazeny podle své produktivity . Najdete nás pod názvem UCLA_Math; obvykle se pohybujeme někde mezi 40. a 55. místem.
Testování pouze jednoho kandidátního čísla může trvat jednomu stroji měsíce, ale využitím výkonu jednotlivých počítačů připojených k internetu po celém světě lze dosáhnout rychlého pokroku.
Otázka: Jaká je pravděpodobnost, že objevíte Mersenne Prime?
Odpověď: Podle projektu GIMPS, pravděpodobnost , že se jakékoli číslo kandidáta ukáže jako Mersenne Prime , je 1 ku 150 000.
Otázka: Jak vlastně testujete čísla, abyste zjistili, zda jsou to Mersenne Primes?
Odpověď: Existuje mnoho čísel ve tvaru 2 P - 1, ale jen velmi málo z nich jsou Mersennova prvočísla. Existuje řada technik, jak otestovat tato čísla, aby se zjistilo, zda se jedná o Mersennova prvočísla, ale počáteční metodou je pokusit se faktorizovat kandidátský exponent P a poté zkusit rozložit kandidátské prvočíslo 2 P -1 pomocí nějaká malá prvočísla.
Existuje 75 let starý algoritmus zvaný Lucas-Lehmerův test , který je široce uznáván jako nejlepší nástroj pro testování Mersenne Primes. Program Prime95 tuto metodu hojně využívá, stejně jako některé další. Vysvětlení je nad rámec tohoto dokumentu, ale zájemce se může dozvědět více zde.
Otázka: OK, proč lidé hledají Mersenne Primes? K čemu jsou dobré?
Odpověď: Ze stejných důvodů, z jakých lidé šplhají po horách, plaví se po neznámých mořích a zkoumají vesmír. Je to výzva! Je vzrušující posouvat hranice výpočetní matematiky a hledat něco neznámého, o čem si myslíte, že tam venku je. Jako bonus, na rozdíl od dávných průzkumníků, můžeme při hledání sedět v pohodlných kancelářských židlích!
To neznamená, že v Mersenne Primes není žádná matematická hodnota. Jsou jistě cenné v oblasti kryptografie a mohou mít další využití, která ještě nebyla objevena.
Výzkumník prvočísel Chris Caldwell zkoumá tento problém hlouběji ve svém článku " Proč lidé nacházejí tato prvočísla? ".
Otázka: Kromě výzvy, proč jste se rozhodli zúčastnit?
Odpověď: Stejně jako na mnoha jiných místech jsme si uvědomili, že naše velká (75 míst) PIC/Math Computer Lab využívá pouze zlomek dostupného výkonu CPU. Místo abychom nechali všechny tyto cykly přijít vniveč, podívali jsme se na řadu distribuovaných počítačových projektů a zjistili jsme, že GIMPS je pro nás nejvhodnější. Kromě toho, že GIMPS je vhod- ný projekt založený na matematice, zjistili jsme, že byl velmi dobře napsaný a nezasahoval do vysokoškolských uživatelů počítačů (to se netýkalo některých jiných projektových softwarů, které jsme zkoumali).
Program v oblasti výpočetní techniky (PIC)přitahuje studenty z velkých oborů z celého kampusu, takže pro nás bylo důležité, aby veškeré počítačové projekty v rámci celé laboratoře byly srozumitelné všem zúčastněným. GIMPS se zde rozhodně hodí a jako bonus jsme si mysleli, že neformální soutěž mezi weby GIMPS bude pro naše studenty zajímavá a zvýší jejich povědomí o výpočetní matematice.
Otázka: Co jste udělali, abyste to spustili? Bylo to složité?
Odpověď: Software GIMPS Prime95 je z pohledu správy systému velmi přímočarý. Snadno se instaluje a nevyžaduje údržbu.
Software Prime95 vydává pravidelné aktualizace stavu zpracování do centrálních počítačů Primenet. Pokud dojde k výpadku chodu stroje, výpočty se po opětovném zapnutí počítače začnou znovu tam, kde skončily. Pokud je jednotlivá krabice nefunkční po delší dobu, Primenet získá zpět číslo a přidělí ho někomu jinému a přidělí nové číslo, když se stroj vrátí do provozu.
Otázka: Jak ověření funguje?
Odpověď: Když je Mersenne Prime nalezen, formální oznámení není učiněno, dokud nezávislá třetí strana neověří nárok. U výjimečně velkých čísel, jako jsou tato, existuje vždy malá šance na výpočetní problém s použitým algoritmem nebo s CPU samotného počítače (Problém s plovoucí desetinnou čárkou Intelje toho klasickým příkladem).
Kvůli těmto potenciálním problémům jsou Mersenne Primes vždy ověřeny pomocí zcela jiného algoritmu na počítači s jinou architekturou. Ověření může trvat dva týdny nebo déle.
Otázka: Kdy došlo k objevu? Jaký druh počítače byl použit?
Odpověď: UCLA Mersenne Prime byla hlášena 23. srpna 2008 na počítači s názvem zeppelin.pic.ucla.edu , Dell Optiplex 745 se systémem Windows XP s procesorem Intel Core 2 Duo E6600 běžícím na 2,4 GHz. Název „zeppelin“ byl součástí naší řady počítačů Classic Rock Band.
Otázka: Co je to všechno o prize money?
Odpověď: The Electronic Frontier Foundation(EFF), první internetová organizace pro občanské svobody, sponzoruje Cooperative Computing Awards . Tyto ceny mají „povzbudit běžné uživatele internetu, aby přispívali k řešení obrovských vědeckých problémů“, a představují finanční odměny, když jsou dosaženy určité standardy.
EFF má stálou cenu 100 000 $ za první objevené prvočíslo s 10 miliony číslic. UCLA Mersenne Prime má téměř 12,9 milionu číslic a splňuje kritéria pro zadání zakázky. Jakmile budou formální výsledky zveřejněny v příslušném časopise, bude udělena cena. To bude nejdříve v roce 2009.
Podle předchozí dohody, pouze 50 % ceny získá objevitel 10milionového prvočísla. 25 % je vyčleněno na charitu a vzhledem k povaze spolupráce GIMPS bude většina zbývajících 25 % věnována objevitelům dalších Mersenne Primes, přičemž malá částka půjde na samotný GIMPS.
Otázka: Co to slyším o plakátu? Bude nějaký pro UCLA Mersenne Prime?
Odpověď: Společnost s názvem Perfectly Scientific již roky vytváří plakát největšího v současnosti známého explicitního prvočísla. Plakát pro M44, vyrobený v roce 2006, používal extrémně malé písmo k vytlačení 9,8 milionu číslic na jeden plakát o rozměrech 29" x 40". Společnost nabídla spolu s plakátem i klenotnickou lupu, aby se dal číst.
Richard Crandall z Perfectly Scientific mě nedávno kontaktoval, aby mi oznámil, že plakát UCLA Mersenne Prime je nyní k dispozici ke koupi. Stojí 99 $, nezarámovaný a dostupný na webu Perfectly Scientific.
Otázka: A co ten druhý nedávno objevený Mersenne Prime?
Odpověď: Dva týdny poté, co byla objevena UCLA Mersenne Prime, Hans-Michael Elvenich v Německu objevil dalších 10 milionů číslic plus Mersenne Prime. S 11,2 miliony číslic je asi o 10 % menší než UCLA Mersenne Prime.
Není to poprvé, co byly Mersenne Primes objeveny mimo provoz. V roce 1988 Colquitt a Welsh objevili Mersenne Prime menší než předchozí dva, objevené v letech 1983 a 1985.
V době psaní tohoto článku je UCLA Mersenne Prime považována za 46. Mersenne Prime (nazývaná „M46“ komunitou hledající Mersenne Prime), i když to byla 45. objevená. Elvenichova Mersenne Prime je M45, ale byla objevena jako 46.!
Další komplikací je, že nebyly testovány všechny potenciální prvočísla mezi M39 (objeveným v roce 2001) a UCLA Mersenne Prime, takže v budoucnu by jich mohlo být v tomto rozsahu nalezeno více. Pokud ano, bude UCLA Prime „povýšena“ na M47.