PL 
EnglishDomyślny
Українська⚛️ Algorytm Shora
Faktoryzacja kwantowa: wybierz podstawę, znajdź okres r funkcji aˣ mod N za pomocą QFT (część kwantowa), a gcd(a^(r/2)±1, N) ujawni dzielniki. Obserwuj piki QFT w wielokrotnościach Q/r i klasyczne przetwarzanie końcowe.
O tej symulacji
Ta symulacja przechodzi przez algorytm Shora etap po etapie dla małych liczb, których nigdy nie złamałbyś w ten sposób prawdziwym komputerem kwantowym, ale które możesz tu obserwować krok po kroku: wybierz podstawę a względnie pierwszą z N, oblicz ciąg aˣ mod N, znajdź jego okres r (jedyny krok, który prawdziwy komputer kwantowy przyspiesza za pomocą QFT), a następnie weź gcd(a^(r/2)±1, N), by wydobyć dzielniki pierwsze N. Wypróbuj różne wartości N i a, by zobaczyć, kiedy metoda działa czysto, a kiedy wymaga ponownej próby.
🔬 Co pokazuje
Wykres słupkowy aˣ mod N ujawniający powtarzający się okres r oraz symulowany rejestr kwantowy pokazujący piki prawdopodobieństwa skoncentrowane w wielokrotnościach Q/r po kwantowej transformacie Fouriera — wynik pomiaru, który pozwala wydobyć r.
🎮 Jak korzystać
Wybierz N do faktoryzacji i podstawę a, lub kliknij Random a, by automatycznie wybrać taką, która prawdopodobnie się powiedzie, następnie przejdź przez cztery etapy przyciskiem Next stage lub obejrzyj je wszystkie za pomocą Run all stages, albo przejdź do gotowego ustawienia (N=15, 21, 35, 91), by zobaczyć gcd, okres r, piki QFT i końcowe dzielniki.
💡 Czy wiesz, że?
Algorytm Shora nie faktoryzuje N bezpośrednio — jego jedynym prawdziwie kwantowym krokiem jest znalezienie okresu r funkcji aˣ mod N wykładniczo szybciej niż jakakolwiek znana metoda klasyczna; wszystko inne (wybór a, obliczenie gcd) to zwykła arytmetyka klasyczna, dlatego właśnie zagraża szyfrowaniu RSA.
Najczęściej zadawane pytania
Czym jest „okres”, którego szuka ten algorytm?
To najmniejsza dodatnia liczba całkowita r, taka że aʳ mod N = 1. Ponieważ aˣ mod N powtarza się z okresem r, gdy już znasz r, możesz go użyć do algebraicznego wydobycia dzielników N — ta symulacja bezpośrednio uwidacznia ten powtarzający się cykl na wykresie słupkowym.
Dlaczego kwantowa transformata Fouriera ma tu znaczenie?
Znalezienie okresu aˣ mod N klasycznie wymaga sprawdzania wartości jedna po drugiej, co staje się wykładniczo wolne dla dużych N. Komputer kwantowy może przygotować superpozycję wszystkich x naraz i użyć QFT, by wyniki pomiaru skupiały się w wielokrotnościach Q/r, ujawniając r w znacznie mniejszej liczbie kroków.
Dlaczego algorytm czasem wymaga „ponownej próby”?
Jeśli okres r okaże się nieparzysty, lub jeśli a^(r/2) ≡ −1 (mod N), krok gcd nie może wydobyć nietrywialnego dzielnika z tego konkretnego wyboru a — rozwiązaniem jest po prostu wybranie innej podstawy a i ponowna próba, dlatego przycisk „Random a” szuka takiej, która prawdopodobnie zadziała.
Dlaczego ten algorytm zagraża szyfrowaniu RSA?
Bezpieczeństwo RSA opiera się na tym, że obliczeniowo niewykonalne jest rozłożenie na czynniki dużego iloczynu dwóch liczb pierwszych używanego jako klucz publiczny. Algorytm Shora faktoryzuje liczby całkowite wykładniczo szybciej niż najlepsze znane algorytmy klasyczne, więc wystarczająco duży komputer kwantowy uruchamiający go mógłby złamać obecnie bezpieczne klucze RSA.
Jak gcd(a^(r/2)±1, N) właściwie znajduje dzielniki?
Gdy r jest parzyste, a a^(r/2) nie jest ≡ −1 mod N, tożsamość (a^(r/2)−1)(a^(r/2)+1) ≡ 0 (mod N) oznacza, że N musi dzielić wspólny nietrywialny czynnik z co najmniej jednym z tych dwóch członów — obliczenie gcd dla każdego z nich wydobywa ten wspólny czynnik wprost.