Shor-Algorithmus
Der Shor-Algorithmus ist ein Algorithmus zur Faktorisierung großer natürlicher Zahlen auf Quantencomputern: Nur auf solchen Geräten ist er effektiv.Die Bezeichnung ist aber nicht eindeutig, denn Peter W. Shors bahnbrechende Veröffentlichung (aus dem Jahr 1994) enthielt zwei Algorithmen: einen Algorithmus zur Faktorisierung von ganzen Zahlen und einen zur Bestimmung von diskreten Logarithmen.
Allgemein meint die Bezeichnung aber den Algorithmus zur Faktorisierung von großen natürlichen Zahlen: Aus der Zahlentheorie ist bekannt, dass jede natürliche Zahl eine eindeutige Zerlegung in Primfaktoren besitzt. Diese Zerlegung zu finden ist schwierig, aus den Faktoren die Zahl durch Multiplikation herzustellen aber einfach. Diese Asymmetrie ist die Grundlage von modernen Verschlüsselungsverfahren wie RSA. Der Shor-Algorithmus zerstört nun diese Asymmetrie, denn er kann (auf einem Quantencomputer) Zahlen sehr effektiv faktorisieren. Damit stellt er eine Bedrohung für die heutige Kryptografie dar.
Die grundlegende Idee ist, dass man die Faktorisierung auf die Bestimmung der Ordnung zurückführen kann. Und diese Bestimmung lässt sich mit Hilfe der Quanten-Fourier-Transformation effektiv durchführen.
- Eingabe: Eine zusammengesetzte Zahl .
- Ausgabe: Ein nichttrivialer Faktor von .
- Laufzeit: Gatteroperationen.
- Erfolgswahrscheinlichkeit: O(1).
- Ablauf: