Riemannova hypotéza je najznámejší otvorený problém matematiky — a zároveň má konkrétne dôsledky pre bezpečnosť kryptografických systémov založených na distribúcii prvočísel. Prechádzame od zeta funkcie k rozloženiu prvočísel, odtiaľ k RSA a eliptickým krivkám, a nakoniec k otázke: čo by sa reálne stalo, keby bola hypotéza dokázaná alebo vyvrátená.

Abstrakt

Riemannova hypotéza je od roku 1859 nedokázaný výrok o rozložení netriviálnych núl Riemannovej zeta funkcie v komplexnej rovine. Je zároveň jedným zo siedmich Millennium Prize Problems a — čo je pre praktickú kryptografiu dôležitejšie — hlavnou podmienkou najtesnejších dnes známych odhadov hustoty prvočísel. Tento článok ukazuje presne, kde v kryptografických algoritmoch táto hypotéza vstupuje do analýzy: od pravdepodobnostných testov prvočíselnosti pri generovaní RSA kľúčov, cez odhady času behu faktorizačných algoritmov, až po bezpečnostné rezervy eliptických kriviek. V závere odpovedáme na dve otázky, ktoré sa v kuloároch opakujú stále — čo by sa stalo, keby hypotéza bola dokázaná, a čo by sa stalo, keby bola vyvrátená. Odpoveď je v oboch prípadoch pre každodenné IT prostredie prekvapivo pokojná; dôvod, prečo je tomu tak, je obsahom tohto textu.

Kľúčové slová: Riemannova hypotéza, zeta funkcia, distribúcia prvočísel, prime number theorem, RSA, eliptické krivky, Miller–Rabin, post-kvantová kryptografia.

1. Čo hypotéza hovorí

1.1 Riemannova zeta funkcia

V roku 1859 publikoval Bernhard Riemann krátku prácu „Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse” [1]. V nej rozšíril funkciu

$$ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} $$

definovanú pre reálne $s > 1$ Eulerom, na analytickú funkciu v celej komplexnej rovine okrem jedného póĺu v $s = 1$. Toto analytické predĺženie prinieslo s sebou nuly funkcie — body, kde $\zeta(s) = 0$ — a práve tieto nuly sú kľúčové.

Nuly sa rozpadávajú na dve rodiny:

1.2 Hypotéza

Riemann v spomínanej práci vyslovil domnienku, ktorú dnes čítame v jednej vete:

Všetky netriviálne nuly Riemannovej zeta funkcie ležia na kritickej priamke $\mathrm{Re}(s) = 1/2$.

Dnes vieme spočítať prvých desať biliónov netriviálnych núl — všetky ležia na kritickej priamke [2]. Vieme, že na kritickej priamke je ich nekonečne veľa (Hardy, 1914). Vieme, že najmenej 40 % všetkých netriviálnych núl leží na kritickej priamke (Levinson, 1974; Conrey, 1989). Dôkaz, že tam ležia všetky, chýba.

2. Súvis s rozložením prvočísel

Dôvod, prečo matematici po hypotéze siahajú tak dlho, nie je estetika. Rozloženie núl zeta funkcie je ekvivalentné rozloženiu prvočísel na číselnej osi — a to je výsledok, ktorý má praktické dôsledky.

Prime number theorem (Hadamard a de la Vallée Poussin, 1896) hovorí, že počet prvočísel menších alebo rovných $x$, označený $\pi(x)$, sa pre veľké $x$ asymptoticky rovná $\mathrm{Li}(x) = \int_2^x dt/\ln t$. Veta hovorí rádovú rýchlosť konvergencie, nehovorí však, aká veľká môže byť chyba.

Výsledok von Kocha z roku 1901 dáva odpoveď [3]:

Riemannova hypotéza je ekvivalentná odhadu
$|\pi(x) - \mathrm{Li}(x)| = O(\sqrt{x} \ln x)$

To znamená: ak je hypotéza pravdivá, chyba aproximácie prvočíselnej funkcie logaritmickou integrálnou je tak malá, ako to vôbec môže byť. Ak hypotéza pravdivá nie je, chyba môže byť podstatne väčšia — v niektorých oblastiach by sa prvočísla správali odchýlne od predpovede.

Generalizovaná Riemannova hypotéza (GRH) rozširuje tvrdenie na Dirichletove L-funkcie a je silnejší predpoklad — má však priamo kryptografické dôsledky, ktoré nasledujú.

3. Kryptografický dôsledok 1: Generovanie prvočíselných kľúčov

RSA, DSA, Diffie–Hellman a mnohé ďalšie algoritmy potrebujú veľké prvočísla — typicky 1024, 2048 alebo 4096 bitov. Generujú sa tak, že algoritmus vylosuje náhodné číslo požadovanej dĺžky a overí, či je prvočíslom. Overenie je pointa.

3.1 Miller–Rabinov test

Miller–Rabinov test je pravdepodobnostný: pre dané číslo $n$ a náhodne zvolený „svedok” $a$ test odpovie buď „$n$ je zložené” (potom je $n$ skutočne zložené) alebo „nerozhodnutý” (potom je $n$ buď prvočíslo, alebo jedno z vzácnych Carmichael-podobných zložených čísel, ktoré svedka oklamú).

Opakovaným testovaním s rôznymi svedkami sa pravdepodobnosť chyby znižuje: pre $k$ nezávislých testov je horný odhad chyby $4^{-k}$. Pri $k = 40$ je pravdepodobnosť omylu rádovo $10^{-24}$ — v praxi dostatočná.

3.2 Prečo tu vstupuje GRH

Problém nastáva, keď chceme deterministický test — nie pravdepodobnostný. V roku 1976 ukázal Miller [4], že ak platí generalizovaná Riemannova hypotéza, existuje konkrétne množstvo svedkov, ktoré jednoznačne určí prvočíselnosť čísla $n$ — a toto množstvo je polynomiálne v $\log n$. Konkrétne stačí testovať všetkých $a$ do $2(\log n)^2$.

Bez GRH toto tvrdenie nie je dokázané — máme iba Agrawal–Kayal–Saxenov deterministický AKS test (2002), ktorý beží v $O((\log n)^{6+\varepsilon})$. S GRH stačí $O((\log n)^{4+\varepsilon})$.

Praktický dopad: v produkčnej kryptografii používame Miller–Rabin s dostatočným počtom svedkov. Deterministický variant nepotrebujeme. Hypotéza by zvýšila teoretickú čistotu dôkazu, nie by zmenila žiadnu knižnicu OpenSSL.

4. Kryptografický dôsledok 2: RSA a faktorizácia

Bezpečnosť RSA stojí na obťažnosti faktorizácie súčinu dvoch veľkých prvočísel. Najrýchlejší známy klasický algoritmus — General Number Field Sieve (GNFS) — má heuristicky odhadovaný čas behu

$$ \exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1) \right) (\ln n)^{1/3} (\ln \ln n)^{2/3} \right) $$

Tento odhad je heuristický — jeho dôkaz spočíva na niekoľkých neoverených predpokladoch o rozložení hladkých čísel [5]. Jedným z týchto predpokladov je GRH pre istú triedu L-funkcií.

4.1 Čo z toho plynie

Ak GRH platí, odhad času behu GNFS je dokázaný. Ak neplatí, odhad môže byť nesprávny — a to v oboch smeroch. V nepriaznivej variante by GNFS mohol byť rýchlejší ako sa dnes predpokladá, čo by znamenalo prerátanie dĺžok RSA kľúčov. V priaznivej variante by bol pomalší, čo by posilnilo bezpečnostné rezervy.

Historicky sa odhady GNFS dobre zhodovali s empirickými meraniami faktorizačných rekordov. Najväčší verejne faktorizovaný RSA kľúč je RSA-250 (829 bitov, 2020) — čas behu zodpovedal predpovedi. To je silná empirická podpora GRH v tejto oblasti, nie dôkaz.

4.2 Praktická rezerva

NIST a BSI udržujú odporúčania dĺžok RSA kľúčov (2048 bitov pre použitie do 2030, 3072 bitov nad to) [6]. Tieto odporúčania počítajú so 4–5-dekadickou bezpečnostnou rezervou oproti nameraným časom faktorizácie — a sú dostatočne konzervatívne na to, aby prípadné prekvapenie z vyvrátenia GRH neohrozilo produkčné systémy.

5. Kryptografický dôsledok 3: Eliptické krivky

Kryptografia eliptických kriviek (ECC) stojí na obťažnosti diskrétneho logaritmu v grupe bodov eliptickej krivky nad konečným poľom. Rád tejto grupy — počet bodov — je kľúčový pre bezpečnostný odhad.

Hasseova veta ohraničuje tento rád intervalom $|N - (q+1)| \le 2\sqrt{q}$, kde $q$ je rád základného poľa. Konkrétny rád sa počíta algoritmom Schoof–Elkies–Atkin (SEA), ktorý je v súčasnosti najrýchlejší známy postup pre krivky nad veľkými poľami.

5.1 Kde vstupuje GRH

Analýza času behu SEA využíva generalizovanú Riemannovu hypotézu pre L-funkcie eliptických kriviek — Birch–Swinnerton-Dyerova doména, ktorá je sama o sebe nedokázaná. Z GRH plynie, že SEA beží v $O((\log q)^{4+\varepsilon})$; bez nej máme horšie teoretické odhady.

5.2 Praktické dôsledky

Rovnako ako pri RSA: produkčné implementácie ECC používajú štandardné krivky (NIST P-256, P-384, P-521; Curve25519; secp256k1 pre Bitcoin). Rády ich grúp sú vopred spočítané, overené a zdokumentované. Rýchlosť SEA ovplyvňuje len to, ako rýchlo vieme hodnotiť nové krivky — nie bezpečnosť existujúcich.

6. Čo keby bola hypotéza dokázaná

Dôkaz Riemannovej hypotézy — v hypotetickom roku 2027 — by znamenal:

Žiadny TLS handshake, žiadny podpis dokumentu, žiadne verifikovanie Bitcoin transakcie by sa nezmenili.

7. Čo keby bola vyvrátená

Vyvrátenie by znamenalo nájdenie konkrétnej netriviálnej nuly mimo kritickej priamky. Dôsledky:

Prakticky: NIST a BSI by s určitosťou vydali bulletin, odporúčania dĺžok kľúčov by sa potenciálne zvýšili o 128–256 bitov v najbližšom cykle revízie, migrácia by prebehla počas nasledujúcich 2–3 rokov. Žiadny okamžitý alarm.

8. Kvantový kontext — reálne ohrozenie je iné

Reálna hrozba pre RSA a ECC neprichádza od Riemannovej hypotézy, ale od kvantových počítačov. Shorov algoritmus (1994) rieši faktorizáciu aj diskrétny logaritmus v polynomiálnom čase na kvantovom počítači — bez ohľadu na akékoľvek domnienky teórie čísel.

Súčasné kvantové hardvéry nemajú dosť kvalitných qubitov na prelomenie 2048-bitového RSA (vyžadovalo by to rádovo milión fyzických qubitov s nízkou chybovosťou). Odhady, kedy sa toto zmení, sa pohybujú od „do 2035” (optimistické) po „nikdy” (skeptické), s konsenzuálnym intervalom 2035–2045.

Post-kvantová kryptografia (PQC) je priemyselná odpoveď. NIST v auguste 2024 štandardizoval prvé tri PQC algoritmy — ML-KEM (CRYSTALS-Kyber), ML-DSA (CRYSTALS-Dilithium) a SLH-DSA (SPHINCS+) [7]. Prechod kritických systémov na PQC prebieha teraz a Riemannovej hypotézy sa netýka — PQC algoritmy stoja na úplne iných matematických problémoch (mriežky, hashe), ktoré nemajú so zeta funkciou nič spoločné.

9. Záver

Riemannova hypotéza je matematicky nesmierne dôležitá. Kryptograficky je dôležitá menej, než sa zdá. Dôvod je prostý: produkčná kryptografia nestavia na podmienených tvrdeniach. Používa odhady, ktoré sú pre dnešné stavy techniky dostatočne konzervatívne, implementácie, ktoré sú verifikované empiricky, a kľúče, ktoré majú 4–5-dekadickú rezervu voči známym útokom.

Ak sa hypotéza dokáže, pokladníčka v obchode naďalej dotkne terminálom, uskutoční sa TLS 1.3 handshake s ECDHE a nič sa nezmení. Ak sa vyvráti, bude to historický okamih matematiky — a odporúčania NIST sa pravdepodobne v nasledujúcej revízii posunú o pár bitov nahor. V oboch prípadoch zostáva reálnym kryptografickým problémom príchod funkčného kvantového počítača a tempo prechodu kritickej infraštruktúry na post-kvantové algoritmy.

Matematici hovoria „čakáme na dôkaz”, pretože vedia, že z neho vzíde pochopenie, ktoré dnes nemáme. Inžinieri hovoria „pracujeme ďalej”, pretože vedia, že na dôkaze nevisí ich systém. Obe perspektívy sú legitímne a nekonkurujú si.

IOAS pomáha organizáciám plánovať prechod na post-kvantovú kryptografiu, overovať bezpečnosť existujúcich kľúčových manažmentov a správne interpretovať teoretické predpoklady, ktoré stoja za ich kryptografickou vrstvou. Pre otázky: director@ioas.pro.

Literatúra

[1] Riemann, B. (1859): Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse. Monatsberichte der Berliner Akademie, November 1859.

[2] Gourdon, X. (2004): The 10^13 first zeros of the Riemann zeta function, and zeros computation at very large height. Technical report. Dostupné online.

[3] von Koch, H. (1901): Sur la distribution des nombres premiers. Acta Mathematica 24, 159–182. DOI: 10.1007/BF02403071.

[4] Miller, G. L. (1976): Riemann’s Hypothesis and Tests for Primality. Journal of Computer and System Sciences 13(3), 300–317. DOI: 10.1016/S0022-0000(76)80043-8.

[5] Lenstra, A. K.; Lenstra, H. W. (eds., 1993): The Development of the Number Field Sieve. Lecture Notes in Mathematics 1554. Springer.

[6] NIST SP 800-57 Part 1 Rev. 5 (2020): Recommendation for Key Management: Part 1 – General. National Institute of Standards and Technology. DOI: 10.6028/NIST.SP.800-57pt1r5.

[7] NIST FIPS 203, 204, 205 (2024): Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM); Module-Lattice-Based Digital Signature Standard (ML-DSA); Stateless Hash-Based Digital Signature Standard (SLH-DSA). National Institute of Standards and Technology.

[8] Conrey, J. B. (1989): More than two fifths of the zeros of the Riemann zeta function are on the critical line. Journal für die reine und angewandte Mathematik 399, 1–26.

[9] Agrawal, M.; Kayal, N.; Saxena, N. (2004): PRIMES is in P. Annals of Mathematics 160(2), 781–793. DOI: 10.4007/annals.2004.160.781.

[10] Shor, P. W. (1997): Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing 26(5), 1484–1509. DOI: 10.1137/S0097539795293172.