Pomozte rozbít matematický bank

JAN DOBEŠ  MIROSLAV KUREŠ  |  
matematický bank

Wieferich@home

Řadu úloh je totiž možné a vhodné řešit distribucí výpočtů na počítače laiků, kteří si na ně jen stáhnou příslušnou aplikaci. Mezi typické úlohy řešené tímto způsobem patří analýza velkého množství statistických dat, zpětné inženýrství DNA, modelování struktury proteinů nebo zkoumání vesmírného vlnění na přítomnost rádiového signálu mimozemšťanů, což je úkolem zřejmě nejznámějšího projektu SETI@home provozovaného Kalifornskou univerzitou v Berkeley od roku 1999. Právě nyní se rozbíhá nový projekt Wieferich@home, který je z naší české dílny a vznikal na Západomoravské vysoké škole v Třebíči a Vysokém učení technickém v Brně. Jeho úkolem je najít třetí tzv. Wieferichovo prvočíslo. Ta mají řadu pozoruhodných vlastností a poprvé byla zkoumána německým matematikem Arthurem J. A. Wieferichem (*1884 x1954) v souvislosti se slavnou Fermatovou větou. Přestože ta je dnes již dokázána, ukazuje se, že význam Wieferichových prvočísel je mnohem větší, mimo jiné jsou známy aplikace v asymetrických kryptografických systémech.

Trocha rovnic

Pojďme tedy na chvíli do matematiky. Jedním ze základních a matematikům dobře známých výsledků matematické teorie čísel je tzv. malá Fermatova věta. Podle ní pro libovolné prvočíslo p a libovolné číslo x, které není násobkem p, platí xp-1×1 (mod p).Vysvětleme nyní tento zápis. Nejprve připomeňme, že prvočíslo je takové přirozené číslo větší než 1, které nemá vlastní dělitele, tzn. je dělitelné kromě 1 jen sebou samým: seznam prvočísel začíná čísly 2, 3, 5, 7, 11, 13 atd. a není těžké ukázat, že prvočísel je nekonečně mnoho.Zápis xp-1×1 (mod p) vyjadřuje, že po umocnění libovolného čísla na p-1 a následném vydělení číslem p dostaneme jako zbytek po dělení 1. Jako příklad vezměme dejme tomu p=5 a x=3. Spočteme-li 35–1=34=81, máme po dělení 81:5 skutečně zbytek 1.Nyní zvolme x=2. Pak malá Fermatova věta platí pro každé liché prvočíslo, tedy rovnici 2p-1×1 (mod p) splňuje nekonečně mnoho prvočísel p, vlastně všechna prvočísla počínaje 3. Položme si nyní otázku: splňují některá prvočísla také rovnici2p-1×1 (mod p2)?Ještě jednou: po umocnění dvojky na p-1 a následném vydělení druhou mocninou čísla p máme obdržet jako zbytek po dělení 1. Pokud ano, nazveme takové prvočíslo Wieferichovo prvočíslo.

1093 a 3511

Přes usilovné hledání jsou dodnes známa pouhá dvě Wieferichova prvočísla: první číslo 1093 objevil W. Meissner v roce 1913 a druhé číslo 3511 objevil N. G. W. H. Beeger v roce 1922. Od té doby ale jako když utne. Není ani známo, zda Wieferichových prvočísel je konečně či nekonečně mnoho, ba dokonce není známo, zda prvočísel, která Wieferichova nejsou, je konečně či nekonečně mnoho.

Jsou ale publikovány pravděpodobnostní argumenty pro to, že by měla existovat další Wieferichova prvočísla. Nicméně zhruba do 1015 (biliarda) další Wieferichovo prvočíslo kromě zmíněných dvou opravdu neexistuje; horní hranice se pochopitelně s nasazením výpočetní techniky bude dále posouvat, což je i úkolem projektu Wieferich@home, který v jistém smyslu navazuje na kanadský projekt týmu Joshuy Knauera.

Mezi dalšími výsledky o Wieferichových prvočíslech byly v literatuře publikovány některé poznatky o jejich vlastnostech v binární reprezentaci: Wieferichovo prvočíslo nemůže být současně Mersennovo prvočíslo, tedy prvočíslo tvaru 11…11, Wieferichovo prvočíslo nemůže být současně Fermatovo prvočíslo, tedy prvočíslo tvaru 10…01 ani prvočísla jako 100000010000001000000100000 0100000010000001 nemohou být Wieferichovými prvočísly.

Obě Wieferichova dosud známá prvočísla snížená o jedničku mají pravidelnou binární reprezentaci, a sice 010001000100 (=1093–1) a 110110110110 (=3511–1).

Kde stáhnete software pro váš počítač

Projekt Wieferich@home používá dva algoritmy. První je tzv. kompletní test, který poctivě zkoumá všechna prvočísla z daného intervalu, zda splňují, či nesplňují Wieferichovu kongruenci. Druhý, periodický test, se opírá o hypotézu, že i případné další Wieferichovo prvočíslo bude mít pravidelnou binární reprezentaci.

A teď důležité otázky. Jde jen o prestižní úkol, nebo lze výsledek použít i mimo matematiku? Jaké jsou možné aplikace Wieferichových prvočísel? Tým, který problematiku řeší, se dlouhodobě soustředí na problematiku kryptografie založené na eliptických křivkách (ECC), která je modernějším, svižnějším, avšak matematicky náročnějším konkurentem nejrozšířenějšího asymetrického kryptosystému RSA.

Jan Dobeš nabízí ke stažení freeware Eliptik na adresách www.dobesoft.cz/…/eliptik.exe a www.slunecnice.cz/sw/eliptik, který je pomůckou při studiu modulární aritmetiky a principů šifrování nad eliptickými křivkami. A právě pro kryptografii založenou na eliptických křivkách může být důležitá informace o dalším Wieferichovu prvočíslu!Webové stránky samotného projektu Wieferich@home jsou na adrese www.elmath.org.

Nainstalováním aplikace nebrzdíte chod svého počítače ani nejste nijak omezeni ve své práci. V době, kdy by počítač byl jinak nečinný, vám ale nyní bude testovat prvočísla z přiděleného intervalu, zda jsou Wieferichova.Můžete si přitom i zajímavě zasoutěžit: ať už jako jednotlivci, nebo vytvářením týmů. Možná právě váš výpočet bude pro vědu podstatný.

Přes stále rychlejší počítače není výjimkou, že na některé problémy jsou ještě pomalé. Díky internetu může ale pomoci každý z nás. Není známo, zda Wieferichových prvočísel je konečně či nekonečně mnoho, ba ani to, zda prvočísel, která Wieferichova nejsou, je konečně či nekonečně mnoho.

Věta Wieferich 1909 Arthur Josef Alwin Wieferich se narodil 27. dubna 1884 v německém Münsteru. Publikoval pět původních článků, z toho čtyři, které napsal v letech 1908 a 1909, se ukázaly jako důležité pro další rozvoj teorie čísel. V jednom z nich nazvaném Zum letzten Fermatschen Theorem ukazuje souvislost mezi popsanými speciálními prvočísly a nejslavnějším matematickým problémem (zodpovězeným až 23. června 1993 A. Wilesem), velkou Fermatovou větou. (Podle velké Fermatovy věty neexistují pro n>2 taková nenulová celá čísla a, b, c, aby platilo an+bn+cn=0.) Arthur Wieferich se po absolvování univerzity v Münsteru stal středoškolským profesorem a dále ve výzkumu nepokračoval, zemřel 15. září 1954 v Meppenu. Jeho publikované výsledky jsou hluboké a dodnes ceněné. Připomeňme alespoň hlavní větu dokázanou ve zmíněném článku: Je-li p liché prvočíslo, a, b, c nenulová celá čísla taková, že ap+bp+cp=0 a p není dělitelem součinu abc, pak p splňuje 2p-11 (mod p2). Wieferichova prvočísla jsou známa pouze dvě (1093 a 3511) a až zhruba do biliardy neexistuje žádné jiné. Pokud se chcete i vy zúčastnit hledání dalšího Wieferichova prvočísla, můžete se zapojit do českého matematického projektu distribuovaného počítání a pomoci vědě tak po téměř sto letech vyřešit jeden zajímavý problém.

Nejčtenější