(c) Graphicsstock

Riemannova hypotéza a kryptografie

Britský matematik Michael Atiyah tvrdí, že se mu podařilo dokázat Riemannovu hypotézu. Co si o tom máme myslet? Plus pokus o vysvětlení, proč se o bezpečnost šifer sotva třeba bát.

Jak lze zjistit krátkým prohledáváním zdrojů, Atiyahovi je 90 let a uvádí, že se mj. snaží rozbourat tradiční představu o tom, jak produktivita matematiků rychle klesá s věkem.
Co se týče samotného důkazu, jeho správnost samozřejmě my laici naprosto nemáme šanci posoudit. Z toho, že důkaz Riemannovy hypotézy byl ovšem oznámen již několikrát a nikdy se dosud nepotvrdil, lze snad odhadnout, že spíše skepse je prozatím na místě i v tomto případě.
Samotná Riemannova hypotéza se týká výpočtu určité komplexní funkce; na výsledku závisí rozložení prvočísel (respektive maximální odchylka od přibližného rozložení, čímž se zabýval rovněž Riemenann). Riemannova hypotéza patří mezi sedm největších matematických problémů, které americký Clayův ústav prohlásil za hlavní matematické výzvy pro toto století (jde o obdobu největších problémů pro 20. století, které vybral David Hilbert). Z nich již byla prozatím dokázána Poincarého domněnka – nyní tedy již věta. Příslušný důkaz byl dost medializován, protože úspěch zde zaznamenal pološílený (nebo je vhodnějším označením „podivínský“?) ruský matematik Grigorij Perelman, který finanční odměnu odmítl. Pro média představovaly samozřejmě lahůdku související výstřednosti génia – tak lze dohledat, že prý spí na matraci, kterou našel u popelnic, z jeho petrohradského bytu se k sousedům šíří hmyz apod.
Zpět k údajnému důkazu Riemannovy domněnky. Hlavní otázka kladená v této souvislosti zní: Znamenal by eventuální důkaz něco pro kryptografii, respektive pro tu její část, kde lámání příslušné šifry odpovídá rozkladu obrovského čísla na součin prvočísel (faktorizaci)? Matematik a popularizátor Keith Devlin v této souvislosti uvádí, že obavy o bezpečnost šifer jsou nejspíš přehnané. Bez ohledu na platnost Riemannovy hypotézy jsou totiž prvočísla rozložena na ose cca náhodně. Z platnosti věty nijak nevyplývá, jak z prvočísla p(x) získat prvočíslo p(x+1), ani tedy jak nějak efektivně (efektivněji než jinými metodami) ověřit, zda číslo je prvočíslem. Navíc vlastně všichni očekávají, že Riemannova hypotéza platí, dokonce některé kryptografické techniky byly navrženy už s ohledem na její platnost. Problém by mohl vzniknout pouze tehdy, kdyby při důkazu byly – spíše shodou okolností – objeveny/použity prostředky, které by pak umožnily zefektivnit faktorizaci (což by úplně teoreticky bylo mimochodem možné zase naopak i v případě, že by důkaz jako takový byl špatně).

Poznámky:
Česky speciálně na téma Sedmi problémů od Clayova ústavu vyšla kniha
Keith Devlin: Problémy pro třetí tisíciletí: Sedm největších nevyřešených otázek matematiky (Argo a Dokořán 2005, v tuto chvíli rozebráno).
K faktorizaci má ovšem zřejmě mnohem těsnější vztah jiný ze sedmi největších problémů, tzv. P vs. NP – otázka týkající se výpočetní složitosti. U faktorizace přitom víme, že určitě není složitější než NP úplné problémy. Zde by důkaz kryptografické techniky ohrozit mohl, i když opět spíše v tom smyslu, že by při něm byly objeveny nějaké speciální techniky faktorizace (jinak i kdyby se třeba ukázalo, že NP úplné úlohy jsou řešitelné v polynomiálním čase s nějakým obrovským polynomem, samo o sobě by to efektivnější lámání šifer neumožnilo; zde přitom nejde jen o faktorizaci, na příslušné výpočetní asymetrii NP úplných úloh jsou založeny i jiné techniky asymetrické kryptografie).
Mimochodem, ověřit důkaz Poincarého domněnky trvalo matematikům několik let, takže těžko očekávat, že bychom se rychle dozvěděli, jak se to má s důkazem Atiyahovým (leda by se v něm podařilo objevit triviálnější chyby, nebo autor přiznal, že jde o mystifikaci apod.).

Je vesmír Temným lesem?

Vzhledem k tomu, že aktuálně běží seriál podle knižní trilogie Problém tří těles, k myšlenkovému …

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *