Algorytm Shora rozkłada duże liczby całkowite na czynniki wykładniczo szybciej niż jakakolwiek znana metoda klasyczna, znajdując okres r funkcji aˣ mod N dla losowej podstawy a względnie pierwszej z N. Komputer kwantowy znajduje ten okres za pomocą kwantowej estymacji fazy (QPE), a następnie krótkie klasyczne obliczenie algorytmem Euklidesa zamienia r na rzeczywiste czynniki N. Ponieważ RSA i podobne kryptosystemy klucza publicznego opierają się na trudności faktoryzacji, wystarczająco duży komputer kwantowy uruchamiający ten algorytm złamałby je — dlatego właśnie dziś wdraża się kryptografię postkwantową.
Uwaga o uczciwości: symulacja prawdziwego obwodu QPE wymagałaby modelowania wielu kubitów i byłaby zbyt ciężka dla canvasu w przeglądarce. Ta demonstracja wiernie pokazuje klasyczną sekwencję szukania okresu, a następnie rysuje uproszczone, poglądowe „widmo” z pikami przy fazach k/r, jakie dałby prawdziwy pomiar kwantowy — to pomoc dydaktyczna, a nie symulowany obwód kwantowy.
aʳ ≡ 1 (mod N) — r jest rzędem multiplikatywnym a
modulo N. Gdy r jest parzyste i a^(r/2) ≢ −1 (mod N), wyrażenia
gcd(a^(r/2) − 1, N) oraz
gcd(a^(r/2) + 1, N) dają nietrywialne czynniki N.
Peter Shor opublikował ten algorytm w 1994 roku, pokazując po raz pierwszy, że komputery kwantowe mogą rozwiązywać praktycznie istotny problem wykładniczo szybciej niż jakikolwiek znany algorytm klasyczny. Niewielkie demonstracje — rozkładanie takich liczb jak 15 i 21 — były przeprowadzane na prawdziwym fizycznym sprzęcie kwantowym już od wczesnych lat 2000., choć skalowanie do rozmiarów istotnych kryptograficznie pozostaje poważnym wyzwaniem inżynieryjnym.
Algorytm Shora, opublikowany przez matematyka Petera Shora w 1994 roku, to wynik, który zmienił obliczenia kwantowe z teoretycznej ciekawostki w egzystencjalne pytanie dla współczesnej kryptografii. Rozkłada on liczbę złożoną N na czynniki, znajdując okres r ciągu aˣ mod N dla pewnej podstawy a względnie pierwszej z N — zadanie, które komputer kwantowy może wykonać wykładniczo szybciej niż jakakolwiek znana metoda klasyczna, wykorzystując operację zwaną kwantową estymacją fazy (QPE), by odczytać r bezpośrednio ze wzorców interferencyjnych w superpozycji stanów. Gdy r jest już znane, krótkie obliczenie algorytmem Euklidesa, zastosowane do ar/2 ± 1 oraz N, bardzo często ujawnia dwa prawdziwe, nietrywialne czynniki N.
Ma to znaczenie daleko wykraczające poza czystą matematykę: kryptosystem klucza publicznego RSA, który wciąż zabezpiecza znaczną część ruchu internetowego, operacji bankowych i bezpiecznej komunikacji, opiera się całkowicie na założeniu, że faktoryzacja dużych liczb jest obliczeniowo niewykonalna. Wystarczająco duży, odporny na błędy komputer kwantowy uruchamiający algorytm Shora obaliłby to założenie — dlatego właśnie rządy i organizacje standaryzacyjne wdrażają już kryptografię postkwantową zaprojektowaną tak, by przeciwstawić się atakom kwantowym. Ten symulator przeprowadza przez klasyczną sekwencję szukania okresu, poglądowe odtworzenie widma kwantowego, jakie zmierzyłaby QPE, oraz rzeczywistą arytmetykę algorytmu Euklidesa, która zamienia okres na faktoryzację — na małych, sprawdzalnych ręcznie przykładach N = 15, 21 i 35.
Rozkłada liczbę złożoną N na czynniki pierwsze. Klasycznie najlepsze znane algorytmy faktoryzacji dużych liczb działają w czasie rosnącym niemal wykładniczo wraz z liczbą cyfr, dlatego szyfrowanie RSA, oparte na trudności faktoryzacji, pozostawało bezpieczne przez dziesięciolecia. Algorytm Shora rozkłada N w czasie rosnącym jedynie wielomianowo — wykładnicze przyspieszenie dla wystarczająco dużych N.
Jeśli a jest względnie pierwsze z N, a r jest parzyste i ar/2 nie jest przystające do −1 modulo N, to ar/2 − 1 oraz ar/2 + 1 są świadectwem tego, że N dzieli ich iloczyn, ale nie każdy czynnik z osobna. Algorytm Euklidesa, zastosowany do gcd(ar/2 − 1, N) oraz gcd(ar/2 + 1, N), wyodrębnia wtedy prawdziwy nietrywialny czynnik N bezpośrednio z tego faktu arytmetycznego.
Nie, i ta strona mówi o tym wprost. Symulacja prawdziwego obwodu kwantowej estymacji fazy, który znajduje r, wymagałaby modelowania wielu kubitów, co znacznie przekracza możliwości canvasu w przeglądarce. Zamiast tego ta demonstracja oblicza r klasycznie za pomocą zwykłej pętli, a następnie rysuje poglądowe „widmo” z pikami przy k/r, aby w celach dydaktycznych pokazać, jak wyglądałby prawdziwy pomiar QPE.
Konstrukcja oparta na gcd działa tylko wtedy, gdy okres r jest parzysty, a ar/2 nie jest przystające do −1 modulo N. Jeśli r okaże się nieparzyste, albo jeśli obliczenie gcd zwraca tylko trywialne czynniki 1 lub N, wybrana podstawa a po prostu nie działa dla tej metody. Standardowym rozwiązaniem, zarówno tutaj, jak i w prawdziwym algorytmie, jest wypróbowanie innej losowej podstawy a i powtórzenie procedury.