Algorytm faktoryzacji Shora

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Kwantowy algorytm Shoraalgorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie i wykorzystując pamięć , przy wykorzystaniu komputera kwantowego. Algorytm ten stanowi teoretyczne zagrożenie dla powszechnie używanego w internecie kryptosystemu RSA. Klucz publiczny w RSA jest iloczynem dwóch dużych liczb pierwszych. Możliwość efektywnego odtworzenia tych liczb na podstawie klucza publicznego pozwalałaby poznać klucz prywatny i tym samym złamać cały szyfr.

Jak większość algorytmów kwantowych, algorytm Shora jest algorytmem probabilistycznym: zwraca poprawną odpowiedź jedynie z pewnym prawdopodobieństwem. Ponieważ jednak odpowiedź może być szybko sprawdzona, powtarzanie algorytmu umożliwia uzyskanie poprawnej odpowiedzi w sposób efektywny z dowolnie dużym prawdopodobieństwem.

Algorytm ten opublikował Peter Shor w 1994 roku. W 2001 roku grupa informatyków z firmy IBM i Uniwersytetu Stanford zademonstrowała jego działanie na 7-kubitowym komputerze kwantowym opartym o jądrowy rezonans magnetyczny. Dokonano wtedy rozkładu liczby [1]. Faktoryzacji liczby dokonano w 2011 roku[2].

Procedura realizacji[edytuj]

Na wejściu algorytmu dostajemy liczbę naturalną . Naszym zadaniem jest znalezienie liczby między a , która dzieli bez reszty.

Algorytm Shora składa się z dwóch części:

  1. Sprowadzenia problemu faktoryzacji do problemu znajdowania rzędu elementu w grupie – realizowanego na klasycznym komputerze.
  2. Znajdowania rzędu elementu za pomocą algorytmu kwantowego.

Część klasyczna[edytuj]

  1. Wylosować liczbę .
  2. Obliczyć – na przykład za pomocą algorytmu Euklidesa.
  3. Jeśli , to został znaleziony nietrywialny dzielnik i można zakończyć część klasyczną.
  4. W przeciwnym wypadku należy użyć podprocedury znajdującej , które jest okresem następującej funkcji:
    ,
    czyli znależć najmniejsze naturalne , takie że .
  5. Jeśli jest nieparzyste, wrócić do punktu 1.
  6. Jeśli , wrócić do punktu 1.
  7. Dzielnikiem jest . Koniec algorytmu.

Część kwantowa: Znajdowanie okresu funkcji[edytuj]

Obwód kwantowy algorytmu faktoryzacji Shora
  1. Przygotować dwa rejestry kwantowe: wejściowy i wyjściowy, każdy z kubitów, i zainicjować je na stan:
    dla od do .
  2. Skonstruować układ realizujący funkcję w postaci kwantowej i zaaplikować ją do powyższego stanu, otrzymując:
  3. Zaaplikować odwróconą kwantową transformatę Fouriera do rejestru wejściowego. Transformata ta jest zdefiniowana wzorem:
    Efektem tej operacji będzie zatem stan:
  4. Dokonać pomiaru, otrzymując w rejestrze wejściowym i w rejestrze wyjściowym.
    Ponieważ jest okresowa, prawdopodobieństwo uzyskania pary wynosi:
    Można policzyć, że to prawdopodobieństwo jest tym większe, im wartość jest bliższa liczbie całkowitej.
  5. Przekształcić w nieskracalny ułamek i wziąć jego mianownik jako kandydata na .
  6. Sprawdzić czy . Jeśli tak, algorytm jest zakończony.
  7. Jeśli nie, sprawdź innych kandydatów na , przez użycie wartości blisko , albo wielokrotności . Jeśli któryś z kandydatów działa, algorytm jest zakończony.
  8. Jeśli nie udało się znaleźć dobrego , wróć do punktu 1.

Analiza algorytmu[edytuj]

Część klasyczna[edytuj]

Liczby naturalne mniejsze od i względnie pierwsze z z mnożeniem modulo tworzą grupę skończoną. Każdy element należący do tej grupy ma więc jakiś skończony rząd – najmniejszą liczbę dodatnią taką że:

.

Zatem . Jeśli potrafimy obliczyć i jest ono parzyste, to:

.

Skoro jest najmniejszą liczbą taką że , to nie może dzielić . Jeśli nie dzieli również , to musi mieć nietrywialny wspólny dzielnik z obiema liczbami: i .

Otrzymujemy w ten sposób jakąś faktoryzację . Jeśli jest iloczynem dwóch liczb pierwszych, jest to jego jedyna faktoryzacja.

Część kwantowa[edytuj]

Algorytm znajdowania okresu funkcji bazuje na zdolności komputera kwantowego do jednoczesnych obliczeń na wielu stanach. Obliczamy wartość funkcji jednocześnie dla wszystkich wartości , uzyskując superpozycję wszystkich wartości.

Fizyka kwantowa nie umożliwia nam jednak bezpośredniego odczytania tych informacji. Każdy pomiar niszczy superpozycję, pozwalając nam odczytać tylko jedną z wartości. Zamiast odczytywać te wartości, dokonujemy transformacji Fouriera – która zamienia wartości funkcji na wartości jej okresów. Późniejszy odczyt daje z dużym prawdopodobieństwem wartość bliską jakiemuś okresowi funkcji.

Do wykonania kwantowego algorytmu niezbędna jest kwantowa implementacja trzech operacji:

  1. Stworzenia superpozycji stanów.
    Można tego łatwo dokonać aplikując bramki Hadamarda do wszystkich kubitów w rejestrze.
  2. Funkcji jako funkcji kwantowej.
    Używany do tego jest algorytm szybkiego potęgowania, w wersji modulo . Należy zauważyć że ten krok jest najtrudniejszy w implementacji, i wymaga dodatkowych kubitów i największej ilości kwantowych bramek logicznych.
  3. Odwrotnej kwantowej transformacji Fouriera.
    Używając kontrolowanych bramek obrotu i bramek Hadamarda, Shor zaprojektował układ, który realizuje to przy użyciu bramek.

Po zastosowaniu tych przekształceń, pomiar stanu rejestru da przybliżoną wartość okresu .

Przykładowo załóżmy dla uproszczenia, że istnieje takie , że jest całkowite. Wtedy prawdopodobieństwo uzyskania dobrego jest równe 1. Aby to pokazać, wystarczy zauważyć, że

dla dowolnego całkowitego .

Zatem suma czynników dających wartość będzie równa , bo istnieje różnych wartości dających ten sam wykładnik. Prawdopodobieństwo każdego takiego wynosi zatem . Istnieje różnych takich, że jest całkowite, oraz różnych możliwych wartości . W sumie prawdopodobieństwo uzyskania dobrego wynosi zatem 1.

Przypisy

Literatura[edytuj]

Oryginalna praca Shora:

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

Podręcznik obliczeń kwantowych:

Quantum Computation and Quantum Information, Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000