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 bisher (Stand 2020) keine hinreichend großen und fehlerarmen Quantencomputer zur Verfügung stehen. Um eine Zahl mit Binärstellen (d. h., ) zu faktorisieren, benötigt ein Quantencomputer ein Quantenregister, dessen Größe mindestens linear mit der Zahl der Binärstellen wächst. Der ursprüngliche Algorithmus von Shor benötigt 3N Qubits, die beste bekannte Variante kommt mit 2N+3 Qubits aus. Diese Zahlen gelten für einen idealen (fehlerfreien) Quantencomputer. In der Praxis ist es nötig, Quantenfehlerkorrekturverfahren zu verwenden. Dann werden um einen (großen, aber in N konstanten) Faktor M mehr physische Qubits benötigt, wobei M sehr stark von der Fehlerrate und dem verwendeten Fehlerkorrekturcode abhängt. Man schätzt, dass für eine 2048-bit-Zahl 10 bis 100 Millionen Qubits benötigt werden (im fehlerfreien Fall wären es nur einige tausend). 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. 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. 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.