DigiZen

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.

· 2 min čítania

Chladiaca „luster“ kvantového počítača IBM Quantum System One – pozlátené stupne kryostatu, ktoré chladia čip takmer na absolútnu nulu. Ilustračná fotografia, nesúvisí priamo so Shorovou prá
Chladiaca „luster“ kvantového počítača IBM Quantum System One – pozlátené stupne kryostatu, ktoré chladia čip takmer na absolútnu nulu. Ilustračná fotografia, nesúvisí priamo so Shorovou prácou. Foto: OJB Quantum / Wikimedia Commons, CC BY 4.0

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