Shor-Algorithmus

Der Shor-Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie, der Mittel der Quanteninformatik benutzt. Er berechnet auf einem Quantencomputer einen nichttrivialen Teiler einer zusammengesetzten Zahl und zählt somit zur Klasse der Faktorisierungsverfahren.

Für praktisch relevante Aufgabenstellungen ist der Shor-Algorithmus noch nicht anwendbar, da er starken technischen Einschränkungen unterliegt. Für eine Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): n benötigt man einen Quantencomputer mit mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \log (n) Qubits. Eine Forschungsgruppe der IBM hat beispielsweise im Jahr 2001 einen Quantencomputer mit sieben Qubits eingesetzt, um die Zahl 15 in die Faktoren 5 und 3 zu zerlegen.^[1]

Der Shor-Algorithmus ist für die Kryptographie sehr bedeutend, weil er einen nichttrivialen Teiler essenziell schneller findet als klassische Algorithmen: Während diese subexponentielle, jedoch deutlich höher als polynomiale Laufzeit benötigen, hat der Shor-Algorithmus nur polynomiale Laufzeit. Dies stellt beispielsweise eine Gefahr für die häufig zur verschlüsselten Datenübertragung verwendeten RSA-Kryptosysteme dar, deren Sicherheit gerade auf der Annahme beruht, dass kein Faktorisierungsverfahren mit polynomialer Laufzeit existiert.

Der Algorithmus wurde 1994 von Peter W. Shor veröffentlicht, der damals bei den AT&T Bell Laboratories beschäftigt war. Die Arbeit trägt den Titel Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.^[2] Darin wird auch noch ein zweiter Algorithmus zur Berechnung des diskreten Logarithmus beschrieben, der ebenfalls als Shor-Algorithmus bezeichnet wird. Im Allgemeinen wird diese Bezeichnung jedoch für das Faktorisierungsverfahren verwendet.

Eigenschaften

Der Shor-Algorithmus ist ein probabilistischer Algorithmus. In einigen, je nach Anzahl der Wiederholungen beliebig wenigen Fällen führt er zu keinem Ergebnis; der Algorithmus zählt somit zur Klasse der Monte-Carlo-Algorithmen.

Eingabe: Eine zusammengesetzte Zahl n.
Ausgabe: Ein nichttrivialer Faktor von n.
Laufzeit: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): O\left( (\log\, n)^3 \right) Gatteroperationen.

Ablauf

Die grundlegende Idee ist, dass man die Faktorisierung auf die Bestimmung der Ordnung zurückführen kann. Diese Bestimmung lässt sich mit Hilfe der Quanten-Fouriertransformation effektiv durchführen. Man teilt den Algorithmus deshalb häufig in einen klassischen Teil zur Reduzierung des Problems und einen Quantenteil, der das Restproblem effektiv löst.

Klassischer Teil

Wähle eine Zahl x (1 < x < n).
Bestimme den ggT(x, n) (z.B. mittels des Euklidischen Algorithmus). Falls das Ergebnis ungleich 1 ist, gib dies als Lösung zurück und terminiere. Sonst fahre mit dem nächsten Schritt fort.
Bestimme mit Hilfe des Quantenteils (s.u.) die Ordnung r von x in der primen Restklassengruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): (\mathbb Z/n\mathbb Z)^\times (das kleinste Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): r\in\mathbb{N} , so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^r\equiv 1 (\textrm{mod}\; n) . Schritt 2 stellte sicher, dass ein soches r existiert.
Beginne erneut bei 1, falls:
1. r ungerade ist, oder
2. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^{r/2}\equiv -1 (\textrm{mod}\; n) .
Gib Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \textrm{ggT}(x^{r/2} - 1, n) als Lösung zurück.

Erklärung:

Warum ist der Wert in Schritt 5 eine Lösung? - Betrachte das Produkt (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^{r/2}-1 ) · (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^{r/2} +1 ) = Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^r -1 . Wir wissen nach Schritt 3, dass gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^r -1 ≡ 0 mod n, dass nicht gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^{r/2}+1 ≡ 0 mod n (Schritt 4) und dass nicht gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^{r/2}-1 ≡ 0 mod n (Schritt 3, da r die kleinste Zahl mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^r -1 ≡ 0 mod n ist und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {r/2} < r gilt), woraus folgt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^{r/2} -1 nichttriviale Teiler von n enthält, der euklidische Algorithmus zur Berechnung des ggT liefert diese Teiler in Polynomialzeit.
Wie oft muss man das Verfahren wiederholen, bis man einen Teiler erhält? - Die Wahrscheinlichkeit, bei zufälliger Wahl von x einen Teiler zu erhalten, beträgt mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 1 - 1/2^{k-1} , wobei k die Zahl der voneinander verschiedenen Primfaktoren von n (ungleich 2) ist. Wenn zum Beispiel n aus nur zwei Primfaktoren zusammengesetzt ist, erhält man pro Durchgang mit Wahrscheinlichkeit 1/2 eine Lösung, die Wahrscheinlichkeit für einen Misserfolg nach t Schritten beträgt also nur noch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 2^{-t} .

Quantenteil

Bestimme q als Potenz von 2 mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): n^2 ≤ q < Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 2n^2 .
Initialisiere das erste Quantenregister (Eingaberegister) mit der Superposition (siehe Qubit) aller Zustände a (mod q). Dies führt in den Zustand:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \frac {1}{q^{1/2}} \sum_{a=0}^{q-1} | a \rangle \ | 0 \rangle .
Initialisiere das zweite Register (Ausgaberegister) mit der Superposition der Zustände $x^{a}({\textrm {mod}}\,n)$ . Das Ergebnis ist der Zustand:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \frac {1}{q^{1/2}} \sum_{a=0}^{q-1} | a \rangle \ | x^a (\textrm{mod}\, \ n) \rangle .
Führe auf dem ersten Register die Quanten-Fouriertransformation durch, wobei:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): QFT \left( | a \rangle \right) = \frac {1}{q^{1/2}} \sum_{c=0}^{q-1} e^{2\pi iac/q} \ | c \rangle
so dass sich ergibt:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \frac {1}{q} \ \sum_{a=0}^{q-1} \ \sum_{c=0}^{q-1} e^{2\pi iac/q} \ | c \rangle \ | x^a (\textrm{mod}\, \ n) \rangle .
Führe eine Messung durch (entnimm den Inhalt der Register). Die Wahrscheinlichkeit für den Zustand |c, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): x^k (mod n)⟩ mit 0 < k < r ergibt sich zu:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \left| \frac {1}{q} \ \sum_{a: x^a \equiv x^k} e^{2\pi iac/q} \right|_{}^2 . Hierfür gilt die Beziehung a ≡ k mod r oder a = br + k, so dass wir schreiben können:
$\left|{\frac {1}{q}}\ \sum _{b}e^{2\pi i\left(br+k\right)c/q}\right|_{}^{2}$ Diese diskrete Funktion verfügt durch Amplifikation über charakteristische Maxima für Werte einer Variablen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): d \in \mathbb{Z} , die die Beziehung
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \left| \frac {c}{q} - \frac {d}{r} \right| \le \frac {1}{2q} erfüllen. Es lässt sich zeigen, dass es für die angegebenen Beziehungen von q, r und n höchstens einen solchen Wert bei festem c gibt. Damit lässt sich r berechnen, falls d und r teilerfremd sind. (Die Wahrscheinlichkeit für diesen Fall beträgt mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \frac {\phi (r)}{3r} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \Omega\!\left(\frac {1}{\log \log r}\right) , das heißt, wir erhalten r mit hoher Wahrscheinlichkeit nach O (log log r) Wiederholungen.)
Gib den berechneten Wert r′ zurück, wenn er tatsächlich die Ordnung von x ist, ansonsten wiederhole das Experiment.

Ein ganz anderes Problem, bei dem Quantencomputer ebenfalls eine wesentliche Beschleunigung bringen, betrifft die Suche einer sehr großen, unsortierten Datenbank (siehe Grover-Algorithmus).

Literatur

IBM's Test-Tube Quantum Computer Makes History; First Demonstration Of Shor's Historic Factoring Algorithm - ScienceDaily, 20. Dezember 2001

Quellen

↑ Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood und Isaac L. Chuang: Experimental realization of an order-finding algorithm with an NMR quantum computer. In: Nature. 414/2001. Macmillan Publishers, S. 883–887, ISSN 0028-0836 (doi:10.1038/414883a)
↑ Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In: SIAM Journal on Computing. 26/1997, S. 1484–1509 (arXiv:quant-ph/9508027)

[VANDER-1] Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood und Isaac L. Chuang: Experimental realization of an order-finding algorithm with an NMR quantum computer. In: Nature. 414/2001. Macmillan Publishers, S. 883–887, ISSN 0028-0836 (doi:10.1038/414883a)

[SHOR-2] Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In: SIAM Journal on Computing. 26/1997, S. 1484–1509 (arXiv:quant-ph/9508027)

[1]

[2]