AI
Shorov algoritmus: rok, keď sa z kvantového počítača stala hrozba pre šifrovanie
Jediný algoritmus z roku 1994 dal dátum spotreby šifrovaniu, ktoré chráni internetové bankovníctvo, šifrované stránky aj digitálne podpisy. Stačí naň dosť veľký kvantový počítač – a odhad, aký veľký, klesol z 20 miliónov qubitov v roku 2019 pod milión v roku 2025.
Z archívu · 1994 · Kvantové počítače · Peter Shor · sympózium IEEE FOCS 1994, rozšírená verzia SIAM J. Computing 1997
Shorov algoritmus · faktorizácia a diskrétny logaritmus
Rytmus skrytý v čísle
Jediný algoritmus z roku 1994 dal dátum spotreby šifrovaniu, ktoré chráni internetové bankovníctvo, šifrované stránky aj digitálne podpisy. Stačí naň dosť veľký kvantový počítač – a odhad, aký veľký, klesol z 20 miliónov qubitov v roku 2019 pod milión v roku 2025.
Veľká časť bezpečnosti internetu (bankovníctvo, šifrované stránky, digitálne podpisy) stojí na jednoduchej asymetrii: vynásobiť dve veľké prvočísla je ľahké, ale z výsledku ich spätne nájsť je pre bežný počítač beznádejne pomalé.
Peter Shor v roku 1994 ukázal, že kvantový počítač by tento problém vedel riešiť rýchlo. Trik je v tom, že rozklad čísla sa dá previesť na hľadanie periódy, podobne ako keď hľadáš, po koľkých úderoch sa opakuje rytmus. A kvantový počítač vie periódy hľadať výnimočne efektívne, lebo pracuje s mnohými možnosťami naraz a interferenciou zosilní tú správnu.
Dovtedy boli kvantové počítače zaujímavosťou pre fyzikov. Po Shorovi sa stali otázkou bezpečnosti štátov aj bánk.
Od FOCS 1994 po Gidneyho odhad
Algoritmus rozkladá zložené čísla v polynomiálnom čase, čím zaraďuje faktorizáciu do triedy BQP – kým najlepší známy klasický postup, všeobecné číselné sito, beží v subexponenciálnom čase.
Shor predstavil algoritmus v roku 1994 na sympóziu IEEE FOCS, rozšírená verzia vyšla v roku 1997 v SIAM Journal on Computing. Faktorizácia sa najprv klasicky prevedie na hľadanie rádu, teda periódy. Kvantová časť použije kvantový odhad fázy na operátor modulárneho násobenia a periódu potom klasicky dopočíta metóda reťazových zlomkov. Najpomalšou časťou je v praxi modulárne umocňovanie, nie samotná kvantová Fourierova transformácia.
V roku 2001 IBM rozložilo malé číslo na 7-qubitovom NMR počítači a neskôr nasledovali fotonické, polovodičové aj iónové pokusy. Podľa Wikipédie žiadny z nich nespĺňa plné požiadavky algoritmu a niektoré využívali vopred známu odpoveď. Odhady pre prelomenie 2048-bitového RSA pritom klesajú: kým odhad z roku 2019 počítal s 20 miliónmi zašumených qubitov a ôsmimi hodinami, Craig Gidney v máji 2025 ukázal cestu s menej než miliónom qubitov za necelý týždeň pri chybovosti operácií 0,1 %.
Šifry s dátumom spotreby
Shor zmenil kvantové počítanie z teoretickej kuriozity na praktickú hrozbu. Spustil tým celé odvetvie postkvantovej kryptografie, ktorá dnes postupne nahrádza RSA a eliptické krivky.
Zaujímavá je dĺžka cesty od dôkazu k stroju: po vyše tridsiatich rokoch sa reálne rozkladajú len malé čísla. Zároveň však lepšie algoritmy a opravy chýb zlacňujú útok rýchlejšie, než rastie hardvér.
Pre bežného človeka: šifrovanie, ktoré dnes chráni internetové bankovníctvo či správy, má dátum spotreby a každý nový odhad zdrojov ho posúva bližšie. Preto banky, štáty a technologické firmy už teraz prechádzajú na nové, postkvantové šifry – zväčša bez toho, aby si to používateľ všimol.
Zdroj: Wikipedia: Shor's algorithm · Gidney 2025, arXiv:2505.15917
Originál: Shor, arXiv:quant-ph/9508027