Shorův algoritmus

Shorův algoritmus (čte se Šórův) je kvantový faktorizační algoritmus velmi efektivní při hledání dělitelů velkých čísel. Jedná se o jeden z vůbec nejdůležitějších algoritmů pro kvantové počítače, protože svou rychlostí významně převyšuje všechny dosud známé algoritmy pro klasické počítače.^[1] V principu se jedná o implementaci Fermatova algoritmu, která je ale proti své klasické analogii významně urychlena použitím kvantové Fourierovy transformace (KFT).^[2][3] Algoritmus byl vytvořen americkým matematikem Peterem Shorem roku 1994.^[4]

Shorův objev spolu s Groverovým algoritmem ve své době předznamenaly obnovu zájmu o kvantové počítače^[4], protože ukázaly výhodu kvantových počítačů na praktických problémech, které mají i širší použití. Zároveň se nejedná pouze o malou výhodu, protože Shorův algoritmus je (téměř) exponenciálně rychlejší, než nejrychlejší klasické algoritmy prosévání kvadratického tělesa a prosévání obecného tělesa. I malý funkční kvantový počítač by tak byl v této úloze schopen svou rychlostí překonat všechny stávající klasické počítače. Shorův algoritmus získává na kvantových počítačích výhodu díky možnosti použití KFT při řešení úzce souvisejícího problému diskrétního logaritmu.

Postup

Základem pro nalezení netriviálních dělitelů čísla ${\displaystyle N}$ je zde Fermatův algoritmus.^[3] Ten spočívá v nalezení dvojice čísel ${\displaystyle a,b}$, které v modulární aritmetice splňují vztah

${\displaystyle a^{2}\equiv b^{2}\mod N}$,

ze kterého lze za použití vzorečku pro rozdíl dvou čtverců získat rozklad ${\displaystyle N}$ na násobek dvou čísel

${\displaystyle (a+b)(a-b)\equiv 0\mod N}$.

Pokud takový výraz vede na netriviální dělitele ${\displaystyle N}$, je přímo získán výsledek. Místo náhodného hledání dvojice čísel ${\displaystyle a,b}$ lze postup urychlit, pokud položíme ${\displaystyle b=1}$.

Eulerova věta tvrdí, že pro libovolná dvě přirozená nesoudělná čísla ${\displaystyle a,N}$ lze najít celočíselný exponent ${\displaystyle r}$, díky kterému je splněna rovnost ${\displaystyle a^{r}\equiv 1\mod N}$. Pokud navíc najdeme sudé ${\displaystyle r}$^{[pozn. 1]}, pak právě bylo nalezeno řešení, protože hledanou dvojicí čísel je ${\displaystyle a^{r/2},1}$ právě když platí ${\displaystyle a^{r/2}\not \equiv 1\mod N}$ (v takovém případě bychom našli pouze triviální řešení ${\displaystyle 0\equiv 0\mod N}$).^[3] Lze ukázat, že pravděpodobnost nalezení vhodného ${\displaystyle a}$ je pro náhodné hodnoty vždy větší než ${\displaystyle 1/2}$^[5], statisticky tak lze očekávat, že neúspěšných pokusů o náhodné nalezení vhodného ${\displaystyle a}$ může být jen několik.

V principu je asymptoticky nejsložitější částí celého postupu nalezení exponentu ${\displaystyle r}$. To je právě obstaráno pomocí KFT, která stejně jako klasická Fourierova transformace hledá periodu v hodnotách ${\displaystyle r}$, po které se ${\displaystyle a^{r}\mod N}$ chová periodicky. Přitom víme, že ${\displaystyle a^{r}\mod N}$ zde musí být periodickou funkcí, protože pro algoritmem hledané ${\displaystyle r}$ platí

${\displaystyle a^{r+R}\equiv a^{r}a^{R}\equiv 1\cdot a^{R}\equiv a^{R}\mod N}$.

Počáteční hodnoty ${\displaystyle a}$ jsou voleny libovolně. Bez předchozí znalosti úspěchu či neúspěchu nelze odhadnout, po kolika opakováních se Shorův algoritmus zastaví, dobu dokončení lze odhadnout pouze dle pravděpodobnosti, kvůli čemuž se Shorův algoritmus řadí mezi algoritmy typu Monte Carlo.

Jak je uvedeno výše, pokud je ${\displaystyle a}$ voleno náhodně, je pravděpodobnost, že pro toto ${\displaystyle a}$ existuje vhodné ${\displaystyle r}$, větší než ${\displaystyle 1/2}$. Samotné nalezení ${\displaystyle r}$ ale také není zaručeno, protože KFT může pro jisté hodnoty neuspět (takových hodnot bývá většina). Celkově vychází, že úspěšnost faktorizace čísla ${\displaystyle N}$ při jednom spuštění KFT je ${\displaystyle {\frac {1}{20}}{\frac {1}{\ln {\ln {N}}}}}$.^[3] Už po řádově několika stovkách spuštění je ale i s touto šancí pravděpodobné, že se faktorizuje číslo, které je délkou srovnatelné s moderními bezpečnostními klíči RSA.

Asymptotické chování

Algoritmus vykazuje polylogaritmickou asymptotickou složitost ${\displaystyle {\mathcal {O}}(\log ^{k}{N})}$.^[5] Pro velké celé číslo ${\displaystyle N}$ je tedy Shorův algoritmus schopný získat jeho prvočíselný rozklad v čase, který je proporční číslu ${\displaystyle \log ^{k}{N}}$.^{[pozn. 2] [6]} Konkrétně je již jednou z existujících verzí dosaženo asymptotiky ${\displaystyle {\mathcal {O}}(\log ^{3}{N})}$ co se počtu logických operací týče.

Původ asymptotického chování Shorova algoritmu je následující: Pro náhodně vybrané ${\displaystyle a}$ a pevné ${\displaystyle N}$ se spustí Euklidův algoritmus, který spočte jejich největší společný dělitel. Pokud je větší než 1, pak byl získán jeden z dělitelů čísla ${\displaystyle N}$. Pro výsledek roven 1 jsou ${\displaystyle a,N}$ nesoudělné a dále se pokračuje dle Fermatova algoritmu. Všechny potřebné algebraické operace i Euklidův algoritmus jsou asymptoticky náročné jako ${\displaystyle {\mathcal {O}}(\log ^{k}{N})}$.^[5]

Jediný problém nastává při hledání exponentu ${\displaystyle r}$. Aby šlo spolehlivě určit periodu ${\displaystyle r}$, je vyžadován počet hodnot alespoň ${\displaystyle {\mathcal {O}}(N^{2})}$.^[5] Na tyto hodnoty se pak aplikuje rychlá Fourierova transformace. Náročnost takové operace je pak u klasických počítačů ${\displaystyle {\mathcal {O}}(N^{2}\log {N})}$,^{[pozn. 3]} ale při použití kvantové verze KFT je náročnost ${\displaystyle {\mathcal {O}}(\log ^{k}{N})}$. KFT je tak původcem celého zrychlení procesu.

Dodnes asymptoticky nejrychlejším klasickým faktorizačním algoritmem je prosévání obecného tělesa, jehož náročnost je ${\displaystyle {\mathcal {O}}\left(\exp {\left((\log {N})^{1/3}(\log {\log {N}})^{2/3}\right)}\right)}$.^[5] Shorův algoritmus tak alespoň teoreticky při hledání dělitelů propůjčuje kvantovým počítačům významné urychlení oproti počítačům klasickým.

Důsledky pro kryptografii

Shorův algoritmus je velmi efektivní při hledání dělitelů velkých čísel, což přímo ohrožuje protokoly s veřejným klíčem, které mohou být prolomeny pomocí vhodného užití KFT, např. RSA nebo ECDSA. První jmenovaný systém přímo pracuje s dešifrováním informací na základě znalosti dělitele velkého čísla.^[7] Druhý jmenovaný nepracuje na základě hledání dělitelů, ale závisí na hledání diskrétního logaritmu, což je problém svázaný s postupem využívaným v Shorově algoritmu.