Hauptmenü öffnen

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 benötigt man einen Quantencomputer mit mindestens Qubits. Eine Forschungsgruppe des US-amerikanischen Unternehmens 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 polynomielle Laufzeit benötigen, hat der Shor-Algorithmus nur polynomielle 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 polynomieller Laufzeit existiert.

Der Algorithmus wurde 1994 von Peter 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.

EigenschaftenBearbeiten

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  .
  • Ausgabe: Ein nichttrivialer Faktor von  .
  • Laufzeit:   Gatteroperationen.

AblaufBearbeiten

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 effizient löst.

Klassischer TeilBearbeiten

  1. Wähle eine Zahl   mit  .
  2. Bestimme den   ,  (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.
  3. Bestimme mit Hilfe des Quantenteils (s. u.) die Ordnung   von   in der primen Restklassengruppe   (das kleinste  , so dass  ). Schritt 2 stellte sicher, dass ein solches   existiert.
  4. Beginne erneut bei 1, falls:
    1.   ungerade ist, oder
    2.  .
  5. Gib   als Lösung zurück.

Lösung im letzten SchrittBearbeiten

Betrachte das Produkt ( ) · ( ) =  . Wir wissen nach Schritt 3, dass gilt:  , dass nicht gilt:   (Schritt 4) und dass nicht gilt:   (Schritt 3, da   die kleinste Zahl mit   ist und   gilt), woraus folgt, dass   nichttriviale Teiler von   enthält, der euklidische Algorithmus zur Berechnung des   liefert diese Teiler in Polynomialzeit.

Anzahl Iterationen für die TeilerfindungBearbeiten

Die Wahrscheinlichkeit, bei zufälliger Wahl von   einen Teiler zu erhalten, beträgt mindestens  , wobei   die Zahl der voneinander verschiedenen Primfaktoren von   (ungleich 2) ist. Wenn zum Beispiel   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   Schritten beträgt also nur noch  .

QuantenteilBearbeiten

  1. Bestimme   als Potenz von 2 mit  .
  2. Initialisiere das erste Quantenregister (Eingaberegister) mit der Superposition (siehe Qubit) aller Zustände   (  ist eine Zahl kleiner als  ). Dies führt in den Zustand:
     .
  3. Initialisiere das zweite Register (Ausgaberegister) mit der Superposition der Zustände  . Das Ergebnis ist der Zustand:
     .
  4. Führe auf dem ersten Register die Quanten-Fouriertransformation durch, wobei:
     
    so dass sich ergibt:
     .
  5. Führe eine Messung durch (entnimm den Inhalt der Register). Die Wahrscheinlichkeit für den Zustand   mit   ergibt sich zu:
     . Hierfür gilt die Beziehung   oder  , so dass wir schreiben können:
      Diese diskrete Funktion verfügt durch Amplifikation über charakteristische Maxima für Werte einer Variablen  , die die Beziehung
      erfüllen. Es lässt sich zeigen, dass es für die angegebenen Beziehungen von   und   höchstens einen solchen Wert bei festem   gibt. Damit lässt sich   berechnen, falls   und   teilerfremd sind. (Die Wahrscheinlichkeit für diesen Fall beträgt mindestens   oder  , das heißt, wir erhalten   mit hoher Wahrscheinlichkeit nach   Wiederholungen.)
  6. Gib den berechneten Wert   zurück, wenn er tatsächlich die Ordnung von   ist, ansonsten wiederhole das Experiment.

LiteraturBearbeiten

EinzelnachweiseBearbeiten

  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, S. 883–887, doi:10.1038/414883a
  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