Wikipedia · einfach zusammengefasst · Stand
Shor-Algorithmus
Er berechnet einen nichttrivialen Teiler einer zusammengesetzten Zahl und zählt somit zur Klasse der Faktorisierungsverfahren. Er ist einer der wichtigsten …
Inhalt6 Abschnitte
Kernidee und Bedeutung
Der Shor-Algorithmus ist ein Faktorisierungsverfahren aus der Zahlentheorie, das Mittel der Quanteninformatik verwendet. Er berechnet zu einer zusammengesetzten Zahl n einen nichttrivialen Teiler, also einen Faktor, der weder 1 noch n selbst ist. Der Algorithmus gehört zu den wichtigsten Quantenalgorithmen.
Seine Bedeutung liegt vor allem in der Kryptographie: Er findet nichttriviale Teiler wesentlich schneller als klassische bekannte Algorithmen. Klassische Verfahren benötigen subexponentielle, aber deutlich mehr als polynomielle Laufzeit; der Shor-Algorithmus hat dagegen polynomielle Laufzeit. Damit wäre er eine Gefahr für RSA-Kryptosysteme, deren Sicherheit auf der Annahme beruht, dass es kein Faktorisierungsverfahren mit polynomieller Laufzeit gibt.
Der Algorithmus wurde 1994 von Peter Shor veröffentlicht. Die zugrunde liegende Idee ist, die Faktorisierung auf die Bestimmung einer Ordnung zurückzuführen. Diese Ordnung kann auf einem Quantencomputer mit Hilfe der Quanten-Fouriertransformation effizient bestimmt werden.
Eigenschaften und praktische Grenzen
Der Shor-Algorithmus ist probabilistisch: Er liefert nicht in jedem Durchlauf ein Ergebnis, kann aber durch Wiederholung mit beliebig hoher Erfolgswahrscheinlichkeit eingesetzt werden. Er gehört damit zur Klasse der Monte-Carlo-Algorithmen. Die Eingabe ist eine zusammengesetzte Zahl n, die Ausgabe ein nichttrivialer Faktor von n. Die Laufzeit beträgt O((log n)^3) Gatteroperationen.
Für praktisch relevante Aufgaben ist der Algorithmus mit Stand 2020 nicht anwendbar, weil keine ausreichend großen und fehlerarmen Quantencomputer verfügbar sind. Um eine Zahl n mit N Binärstellen, also n < 2^N, zu faktorisieren, braucht ein Quantencomputer ein Quantenregister, dessen Größe mindestens linear mit N wächst. Shors ursprünglicher Algorithmus benötigt 3N Qubits; die beste bekannte Variante kommt mit 2N + 3 Qubits aus, jeweils für einen idealen fehlerfreien Quantencomputer.
In der Praxis sind zusätzlich Quantenfehlerkorrekturverfahren nötig. Dadurch werden um einen großen, aber in N konstanten Faktor M mehr physische Qubits benötigt; M hängt stark von Fehlerrate und Fehlerkorrekturcode ab. Schätzungen nennen für eine 2048-bit-Zahl 10 bis 100 Millionen Qubits, während im fehlerfreien Fall nur einige tausend nötig wären. 2001 nutzte eine IBM-Forschungsgruppe einen Quantencomputer mit sieben Qubits, um die Zahl 15 in die Faktoren 5 und 3 zu zerlegen.
Zahlentheoretische Grundlage
Der Algorithmus ist eine für Quantencomputer angepasste Version eines Algorithmus für Primzahltests von M. O. Rabin aus dem Jahr 1976. Mathematisch wird die Faktorisierung einer Zahl auf die Bestimmung der Ordnung in Z_n zurückgeführt.
Die Ordnung eines Elements x modulo n ist die kleinste natürliche Zahl r, für die x^r ≡ 1 mod n gilt. Im Shor-Algorithmus wird x so gewählt, dass es in der primen Restklassengruppe (Z/nZ)^× liegt; das bedeutet hier, dass x zu n teilerfremd ist und daher eine solche Ordnung r existiert. Der klassische Teil reduziert das Faktorisierungsproblem auf diese Ordnungssuche, während der Quantenteil r effizient bestimmen soll.
Klassischer Ablauf
Zuerst wird eine Zahl x mit 1 < x < n gewählt. Dann berechnet man ggT(x,n), also den größten gemeinsamen Teiler von x und n, zum Beispiel mit dem euklidischen Algorithmus. Ist dieser ggT ungleich 1, dann ist bereits ein nichttrivialer Teiler gefunden und der Algorithmus endet.
Ist ggT(x,n) = 1, wird mit dem Quantenteil die Ordnung r von x in (Z/nZ)^× bestimmt, also das kleinste r ∈ N mit x^r ≡ 1 mod n. Danach wird der Versuch verworfen und neu begonnen, falls r ungerade ist oder falls x^(r/2) ≡ -1 mod n gilt. Andernfalls gibt der Algorithmus ggT(x^(r/2)+1,n) als Lösung zurück.
Warum der letzte Schritt funktioniert: Aus x^r - 1 = (x^(r/2)-1)(x^(r/2)+1) und x^r ≡ 1 mod n folgt, dass n das Produkt teilt. Gleichzeitig sind nach den vorherigen Bedingungen weder x^(r/2)+1 noch x^(r/2)-1 allein durch n teilbar. Deshalb enthalten diese Faktoren nichttriviale Teiler von n, die der euklidische Algorithmus in Polynomialzeit finden kann.
Erfolgswahrscheinlichkeit
Bei zufälliger Wahl von x ist die Wahrscheinlichkeit, keinen Teiler zu erhalten, höchstens 1/2^(k-1), wobei k die Anzahl der voneinander verschiedenen Primfaktoren von n außer 2 ist.
Im schlechtesten Fall, wenn n aus nur zwei Primfaktoren zusammengesetzt ist, erhält man pro Durchgang mit Wahrscheinlichkeit 1/2 eine Lösung. Die Wahrscheinlichkeit, nach t Durchgängen immer noch keinen Erfolg zu haben, beträgt dann 1/2^t. Durch Wiederholung kann die Erfolgswahrscheinlichkeit also schnell erhöht werden.
Quantenteil
Im Quantenteil wird die Ordnung r von x modulo n bestimmt. Dazu wählt man q als Potenz von 2 mit n^2 ≤ q < 2n^2. Das erste Quantenregister wird als Superposition aller Zustände a mod q initialisiert, wobei a < q ist. Der Zustand lautet 1/q^(1/2) · Σ_(a=0)^(q-1) |a⟩ |0⟩.
Das zweite Register wird mit den Werten x^a mod n verknüpft. Dadurch entsteht 1/q^(1/2) · Σ_(a=0)^(q-1) |a⟩ |x^a mod n⟩. Anschließend wird auf dem ersten Register die Quanten-Fouriertransformation angewendet. Sie ist definiert durch QFT(|a⟩) = 1/q^(1/2) · Σ_(c=0)^(q-1) e^(2πiac/q) |c⟩.
Nach der Messung erhält man Werte, aus denen Informationen über r gewonnen werden können. Für geeignete ganze Zahlen d treten durch Amplifikation charakteristische Maxima auf, die die Beziehung |c/q - d/r| ≤ 1/(2q) erfüllen. Unter den angegebenen Bedingungen an q, r und n gibt es für festes c höchstens einen solchen Wert. Daraus lässt sich r berechnen, falls d und r teilerfremd sind.
Die Wahrscheinlichkeit dafür beträgt mindestens φ(r)/(3r) oder Ω(1/log log r). Daher erhält man r mit hoher Wahrscheinlichkeit nach O(log log r) Wiederholungen. Der berechnete Wert r′ wird nur zurückgegeben, wenn er tatsächlich die Ordnung von x ist; sonst wird das Experiment wiederholt.