Algorytm Shora: Rozkład na czynniki poprzez znalezienie okresu

Rozkład jest trudny, ale rzeczywistym celem jest znalezienie okresu

Mnożenie dwóch dużych liczb pierwszych daje wynik łatwo obliczalny; w przeciwnym kierunku, znanie tylko iloczynu i jego rozkładu na czynniki liczb pierwsze jest, jak dowodzono, eksponejncjielnie trudne dla klasycznego komputera przy rosnących liczbach. Algorytm Petera Shora z 1994 roku nie atakuje bezpośrednio rozkładu na czynniki. Zdobywa to cel poprzez deturę przez całkowicie inny problem - znalezienie okresu ciężkojednorodnej sekwencji - rozwiązując go eksponejncjielnie szybciej na komputerze kwantowym, a następnie kończąc zadanie za pomocą zwykłych klasycznych operacji arytmetycznych.

Z rozkładu N na czynniki do okresu a^x mod N

Aby rozłożyć nieparzystą złożoną liczbę N (która nie jest potęgą liczby pierwszej), wybierz losową liczbę całkowitą a z zakresu od 1 do N, taką że gcd(a, N) = 1. Czytelnik może być pewien, że ciąg a¹ mod N, a² mod N, a³ mod N, ... jest okresowy - musi w końcu się powtarzać, ponieważ istnieje tylko N możliwych reszt z dzielenia - i jego okres r to taką liczbę, o którą teoria liczb mówi, że jest wielokrotnością aditwną a modulo N:

a^x mod N jest okresowy w x z pewnym okresem r, a^r ≡ 1 (mod N) jeśli r jest PARNE i a^(r/2) ≠ -1 (mod N): p = gcd( a^(r/2) - 1 , N ) q = gcd( a^(r/2) + 1 , N ) z prawdopodobieństwem bliskim 1, p i q są niebanalnymi czynnikami N Tę ostatnią kroką algebra jest banalna: jeśli r jest parzyste, a^(r/2) to niebanalny pierwiastek kwadratowy z 1 modulo N, a N | (a^(r/2)-1)(a^(r/2)+1) bez tego, że N dzieli żaden z czynników osobno - co obliczenie gcd w algorytmie Euklidesa odkrywa bezpośrednio, za czasu wielomianowego, raz znane jest r. Obejmując około połowy wartości a losowo wybranych daje r używalny na pierwszą próbę, a ponowne wybieranie innej wartości a kiedy to nie jest tak, jest tanie, więc całe zadanie rozkładu na czynniki naprawdę sprowadza się do jednego pytania: szybko znajdź r.

a^x mod N  is periodic in x with some period r,   a^r ≡ 1 (mod N)

if r is EVEN and a^(r/2) ≢ -1 (mod N):
    p = gcd( a^(r/2) - 1 ,  N )
    q = gcd( a^(r/2) + 1 ,  N )
    with high probability, p and q are non-trivial factors of N

Dlaczego klasyczne znalezienie okresu jest zablokowane

Znalezienie r klasycznie oznacza obliczanie a^x mod N dla wystarczającej liczby wartości x, aby zauważyć powtarzający się wzór - i dla n-bitowego N, r może być ekspozycyjnie duży w stosunku do n, więc wyszukiwanie brutalne jest bezradne. Nie znane są klasyczne algorytmy, które znalezienie r przekraczabyłyby czas pod-ekspozycyjny (szerszy zbiór pola liczb całkowitych atakuje rozkład bezpośrednio, z podobnym kosztem pod-ekspozycyjnym), co dokładnie jest wąskim miedzianym pasem, który algorytm Shora wykorzystuje poprzez przesunięcie wyszukiwania do rejestrów kwantowych, które mogą reprezentować każdą wartość x jednocześnie.

Cząsteczkowa część: superpozycja, a następnie transformacja

1. załaduj rejestr 1 z równą superpozycją dla x = 0 .. 2^t - 1 2. oblicz a^x mod N i wprowadź wynik do rejestru 2 (współzależnienie dwóch rejestrów) 3. zastosuj Transformację Cząsteczkową Fouriera do rejestru 1 4. pomiar rejestru 1 → wynik jest bliski wielokrotności 2^t / r 5. kontinuowana frakcja czysto klasyka rozszerzona z (wynik / 2^t) odkrywa r Krok 2 umieszcza całą okresową funkcję a^x mod N w superpozycji w jednym przejściu, korzystając z modularnej potęgowania budowanego z cyklicznych kircuitów arytmetycznych. Ponieważ ta funkcja powtarza się okresowo o okresie r, wzór amplitudowy rejestru 1 - po współzależnieniu z rejstrarem 2 - dziedziczy tę samą okresowość. Transformacja Cząsteczkowa Fouriera (patrz nasze towarzyszące artykuły na temat QFT) jest dokładnie narzędziem zaprojektowanym do konwersji okresowości w jednym układzie podstawowym na ostre wachlarze w innym: skupia ona prawdopodobieństwo pomiaru na wynikach bliskich wielokrotnościom 2^t/r, a kontinuowane ułamki - purystycznie klasyka technika stuletnia - wyodrębniają dokładnie ułamek 2^t/r, zatem r, z tego jednego szumu pomiaru z dużą prawdopodobieństwem. Jeśli próba się nie powiedzie (r okazuje się nieparzysty lub daje trywialny czynnik), cały proces jest po prostu ponownie wykonywany dla nowego losowego a - mała stała liczba prób wystarcza na średnim poziomie.

1. load register 1 with an equal superposition over x = 0 .. 2^t - 1
2. compute a^x mod N into register 2 (entangling the two registers)
3. apply the Quantum Fourier Transform to register 1
4. measure register 1 → result is close to a multiple of 2^t / r
5. classical continued-fraction expansion of (result / 2^t) reveals r

Dlaczego RSA się martwi

Bezpieczeństwo zaszyfrowania RSA jest bezpośrednim zakładem, że rozkład iloczynu dwóch dużych liczb pierwszych jest klasycznie niewykonanie. Algorytm Shora działa w czasie wielomianowym względem liczby bitów N - kilka tysięcy gatek kwantowych na kilku tysiącach logicznych, poprawnych qubitów dla klucza 2048-bitowego RSA, zgodnie z obecnymi estymacjami - co by oznaczyło, że ten zakład zostałby wprost naruszone. Budowa komputera kwantowego z wystarczającą liczbą czystych, poprawnych qubitów do uruchomienia algorytmu Shora na zaszyfrowanych kluczach kryptograficznie znaczących pozostaje trudnym problemem inżynieryjnym, nie rozwiązany do dziś, ale istnienie tego algorytmu jest dokładnie tym, dlaczego społeczeństwo kryptograficzne poświęciło ostatni dziesięć lat na standardyzację algorytmów po-kwantowych - schematów opartych na problemach siatek i innych struktur uważanych za odpornościowe zarówno na ataki klasyczne, jak i kwantowe - aby zastąpić RSA i kryptografię krzywych eliptycznych przed dotarciem wystarczająco zdolnego komputera kwantowego.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Shor's Algorithm — Quantum Factoring via Period Finding i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.