Student World

***pravidelné páteční „přetištění“ staršího článku

Keith Devlin, autor i česky vyšlé knihy Jazyk matematiky, popisuje, jaký vztah má řešení Riemannovy hypotézy ke kryptografii.
Riemannova hypotéza popisuje frekvenci rozložení prvočísel mezi „obyčejnými“ čísly – mělo by se řídit jistou komplexní funkcí dzéta, kterou již před Riemannem objevil Euler. Riemann celý problém nadhodil jen tak mimochodem v krátkém článku z roku 1859 – sláva problému tedy v jistém ohledu odpovídá tomu, co nastalo v případě Velké Fermatovy věty, včetně neúspěšného lovu v pozůstalosti obou matematiků. Riemannova hypotéza je navíc jediná z úloh, které mezi největší výzvy matematiky zařadil na počátku 20. století David Hilbert, a které se v téže kategorii nacházejí i o století později.
V čem vlastně spočívá nebezpečí důkazu Riemannovy hypotézy pro současný šifrovací systém s dvojicí klíčů? Určitě ne v potvrzení věty jako takové – prvočísla jsou totiž podle Riemannovy domněnky stále rozložena de facto náhodně (určitá pravidelnost existuje pouze z pohledu „celé osy“, Riemannova hypotéza nám např. nijak neumožňuje rychle získat z n-tého prvočísla prvočíslo následující). Ba dokonce některé kryptografické technologie byly už přímo navrženo s tím, že příslušná hypotéza platí (to je další aspekt – v případě Riemannovy domněnky se všeobecně očekává, že bude dokázána jako pravdivá, skoro nikdo si nemyslí, že je třeba nerozhodnutelná). Za pomoci počítače byla již i ověřena platnost domněnky pro prvních 1,5 miliardy kořenů funkce dzéta.
„Obavy kryptografů vycházejí spíše z toho, že by nové METODY použité k důkazu Riemannovy hypotézy s sebou mohly přinést nový náhled na strukturu prvočísel, který by potom mohl vést ke vzniku lepších faktorizačních metod,“ vysvětluje Keith Devlin.

Možná by v této souvislosti stálo za to se vrátit ke staršímu článku, který se zabýval povahou NP úplných problémů.
(http://www.scienceworld.cz/sw.nsf/ID/15FBA84288D3647EC12570210076F050)
V diskusi o tom, nakolik by objev polynomiálního algoritmu pro řešení NP úplných úloh mohl představovat průlom např. pro faktorizaci, se mj. objevil následující argument: Výsledný polynom by byl nejspíš tak vysokého řádu, že by úloha byla stejně prakticky neřešitelná.
Lze ale zopakovat, že samozřejmě by se nikdo nepokoušel hrubou silou lámat šifry, pokud by stupeň příslušného polynomu byl 35. Jde spíše o něco jiného – při objevu tohoto polynomiálně rostoucího algoritmu by příslušní výzkumníci získali velmi detailní znalost analyzované úlohy. A spolu s tím třeba i nějakou heuristiku pracující v čase rostoucím lineárně nebo kvadraticky… (Jakkoliv se zde zdá být existence takové heuristiky nepravděpodobná.)

autor Pavel Houser