# Shor‑Algorithmus: Wie Quantencomputer die Primfaktorzerlegung revolutionieren
Der **Shor‑Algorithmus** ist der wohl prominenteste Quantenalgorithmus, weil er ein fundamentales Problem der Informatik in *polynomieller Zeit* lösen kann: die **Primfaktorzerlegung großer Zahlen**. Klassische Computer brauchen hierfür exponentiell lange Laufzeiten – das sichert die Sicherheit von RSA und verwandten Kryptosystemen. Peter Shor zeigte 1994, dass Quantencomputer durch periodische Funktionen und die Quanten‑Fourier‑Transformation einen drastischen Zeitvorteil erreichen. Damit ist Shor nicht nur ein Meilenstein der Quanteninformatik, sondern auch ein Weckruf für die Kryptographie. In diesem Artikel erklären wir die Hintergründe, die Schritte des Algorithmus und den aktuellen Stand der Implementierung.
## Warum Primfaktorisierung schwer ist
Eine natürliche Zahl \(N\) lässt sich eindeutig als Produkt von Primzahlen schreiben. Für große semiprime Zahlen (Produkte aus zwei großeren Primzahlen) ist die Zerlegung jedoch extrem aufwändig. Die besten klassischen Algorithmen – wie das **General Number Field Sieve (GNFS)** – haben eine subexponentielle Komplexität von der Form
\[
\exp\Bigl((\log N)^{1/3}(\log\log N)^{2/3}\Bigr).
\]
Für 2048‑Bit‑RSA‑Zahlen bedeutet dies Milliarden Jahre Rechenzeit auf heutigen Maschinen. Genau diese Rechenschwierigkeit ermöglicht **RSA**, **Diffie–Hellman** und Elliptic‑Curve‑Kryptosysteme. Sollte es einen effizienten Faktorisierungsalgorithmus geben, wären diese Verfahren unsicher – daher der Fokus auf **Post‑Quantum‑Kryptographie** (PQC), die wir in einem separaten Artikel erklären.
## Von der Faktorisierung zur Periodensuche
Shor reduzierte die Faktorisierung auf ein Periodenproblem:
1. Wähle zufällig eine Zahl \(a\) mit \(1 < a < N\) und berechne \(\gcd(a,N)\). Wenn der größte gemeinsame Teiler größer als 1 ist, haben wir bereits einen Nichttrivialen Faktor gefunden. 2. Falls \(\gcd(a,N)=1\), betrachte die Funktion \[ f(x) = a^x \bmod N. \] Diese Funktion ist **periodisch** mit der Periode \(r\), d. h. es gilt \(f(x+r) = f(x)\). Die gesuchte Periode \(r\) ist der **Ordnung** von \(a\) modulo \(N\). 3. Kennt man die Periode \(r\) und ist \(r\) gerade, so liefert \[ a^{r/2} \not\equiv -1 \pmod N \] zwei Nichttriviale Faktoren von \(N\) durch \( \gcd\bigl(a^{r/2}-1,N\bigr) \quad\text{und}\quad \gcd\bigl(a^{r/2}+1,N\bigr). \) 4. Sollte \(r\) ungerade oder \(a^{r/2}\equiv -1 \pmod N\) sein, wählt man ein anderes \(a\) und beginnt erneut. Die Kunst liegt also darin, die Periode \(r\) **quantummechanisch** zu bestimmen. Hier kommt die **Quanten‑Fourier‑Transformation (QFT)** ins Spiel. ## Ablauf des Shor‑Algorithmus Der vollständige Shor‑Algorithmus besteht aus **quantum** und **klassischen** Schritten. Wir skizzieren die Prozedur für \(N\) und gewähltes \(a\) mit \(\gcd(a,N)=1\): 1. **Register initialisieren.** Zwei Quantenregister werden benötigt. Das erste Register muss groß genug sein, um Werte bis etwa \(N^2\) darzustellen (es enthält \(t\approx 2\log_2N\) Qubits); das zweite Register beinhaltet das Ergebnis der modularen Potenz \(a^x \bmod N\) und hat \(n=\log_2 N\) Qubits. 2. **Superposition erzeugen.** Das erste Register wird durch Anwendung von Hadamard‑Gates in eine gleichmäßige Superposition von \(|0\rangle\) bis \(|2^t-1\rangle\) gebracht: \[ \frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1}|x\rangle|0\rangle. \] 3. **Modulare Exponentiation.** Eine reversible Quantenroutine berechnet \(f(x)=a^x \bmod N\) und speichert das Ergebnis im zweiten Register, wodurch das zusammengesetzte System entangelt wird: \[ \frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1}|x\rangle|f(x)\rangle. \] Diese Operation ist der aufwändigste Teil und erfordert kontrollierte Multiplikationen und modularen Additionen, implementiert durch Toffoli‑Gates, Kontrollphasen und oft zusätzliche Arbeitsqubits. 4. **Messung des zweiten Registers.** Durch Messen des zweiten Registers kollabiert der Zustand auf alle \(x\) mit demselben Funktionswert. Die verbleibende Superposition im ersten Register besteht aus Gleichständen mit Schrittweite \(r\), also dem gesuchten Periodenabstand: \[ \frac{1}{\sqrt{K}}\sum_{k=0}^{K-1}|x_0 + k r\rangle, \] wobei \(K\approx 2^t/r\). 5. **Quanten‑Fourier‑Transformation.** Nun wird die QFT auf das erste Register angewendet. Diese Transformation wandelt die arithmetische Progression in eine Überlagerung von Zuständen, deren Amplituden bei Vielfachen von \(2^t/r\) konzentriert sind. Explizit ergibt sich ein Zustand \[ \frac{1}{r}\sum_{j=0}^{r-1}\exp\left(2\pi i\,\frac{j x_0}{r}\right)\,|j\cdot 2^t/r\rangle + \text{Rundungsfehler}. \] 6. **Messung und klassische Auswertung.** Man misst das erste Register, erhält ein Ergebnis \(y\) (ein Integer zwischen \(0\) und \(2^t-1\)). Mit großer Wahrscheinlichkeit ist \(y/2^t\) eine Näherung an \(j/r\) für ein zufälliges \(j\). Mittels der **Kettenbruchentwicklung** kann aus dem Bruch \(y/2^t\) der Nenner \(r\) rekonstruiert werden. Anschließend prüft man, ob \(r\) die Bedingungen von oben erfüllt und berechnet die Faktoren. Dieser Ablauf muss unter Umständen mehrmals wiederholt werden, bis ein geeignetes \(a\) und \(r\) gefunden werden. Dennoch ist die erwartete Laufzeit **polynomiell** in \(\log N\). ## Komplexität und Ressourcenbedarf Die Ressourcenanforderungen von Shor sind hoch, aber skalierbar. Für ein \(n\)-Bit‑Zahl \(N\) benötigt der Algorithmus ungefähr \(2n + 3\) qubits. Die Anzahl der Quanten‑Gates ist in der Größenordnung \(\mathcal{O}(n^3)\), dominiert von der modularen Exponentiation. In praktischen Implementierungen sind zusätzliche Arbeitsqubits und tiefe Schaltungen nötig, was für **NISQ‑Geräte** (siehe unseren Artikel zur NISQ‑Ära) eine enorme Herausforderung darstellt. Durch **Fehlerkorrektur** (z. B. Surface‑Codes) kann der Algorithmus gegenüber Rauschen robust gemacht werden, allerdings erhöht sich der Quantenbedarf schnell auf Millionen von physischen Qubits. Schätzungen gehen davon aus, dass für die Faktorisierung einer 2048‑Bit‑Zahl Hunderttausende bis Milliarden physische Qubits erforderlich sind【922387722820920†screenshot】. Dies erklärt, warum man trotz NISQ‑Demonstrationen noch weit von der praktischen Bedrohung großer Kryptosysteme entfernt ist. ## Experimentelle Demonstrationen Seit Shors Vorschlag gab es zahlreiche Demonstrationen in reduziertem Maßstab: * **1999** führten Vandersypen et al. die Faktorisierung von \(N=15\) mit sieben NMR‑Qubits durch. Obwohl das System eigentlich makroskopisch war, zeigte es das Funktionsprinzip. * **2012** implementierte ein Team um Jeremy O’Brien die Faktorisierung von \(N=21\) mit einem photonic Cluster‑State ansatz; vier Photonen dienten als Quantenregister. * **2019** demonstrierte IBM auf dem 7‑Qubit‑Chip „ibmqx5“ eine **variational** compilierte Version von Shor zur Faktorisierung von 21, bei der die QFT durch optimierte Gatter ersetzt wurde. * **2022/2023**: Algorithmen zur Faktorisierung von 35 und 48 mit „compiled Shor“ wurden unter Nutzung von Qiskit und Ion‑Trap‑Technologie realisiert. Diese Experimente verwendeten **Optimierungen** wie **quantum compute–uncompute** und klassische Feedback‑Schleifen, um Ressourcen zu sparen. Alle diese Demonstrationen verwenden stark vereinfachte Schaltkreise oder besondere Eingangsgrößen. Dennoch zeigen sie, dass die Quantenperiodensuche experimentell machbar ist. ## Auswirkungen auf die Kryptografie Die kryptographischen Folgen von Shors Algorithmus sind immens: Sobald hinreichend große, fehlertolerante Quantencomputer verfügbar sind, werden RSA, Diffie–Hellman und Elliptic‑Curve‑Cryptosysteme unsicher. Deswegen ist die **Post‑Quantum‑Kryptografie** (PQC) im Fokus von Standardisierungsgremien wie NIST: Lattice‑basierte, Hash‑basierte oder Code‑basierte Verfahren bieten Sicherheit auch gegen Quantenangriffe. In unserem Beitrag über **Post‑Quantum‑Kryptografie** beleuchten wir die aktuell favorisierten Ansätze und deren Vor‑ und Nachteile. Die Gefahr ist nicht nur theoretisch: Daten, die heute verschlüsselt übertragen werden, könnten abgefangen und gespeichert werden, um sie in Zukunft mit einem Quantencomputer zu entschlüsseln – das sogenannte „Harvest‑now, Decrypt‑later“‑Szenario. Daher sollten Unternehmen bereits jetzt auf PQC umstellen oder hybride Verfahren einsetzen. ## Herausforderungen und offene Fragen Obwohl der Shor‑Algorithmus konzeptionell klar ist, bleiben mehrere Herausforderungen: 1. **Skalierbare Hardware**: Heutige Quantenprozessoren umfassen 50–100 logische qubits und sind stark verrauscht. Für eine praxisrelevante Faktorisierung wird eine fehlerkorrigierte Hardware mit mindestens tausenden logischen qubits benötigt. 2. **Fehlerkorrektur**: Der enorme Ressourcenaufwand für Surface‑Codes oder andere Fehlerkorrekturcodes verlangsamt die Annäherung an nützliche Größenordnungen. Fortschritte in **Fehlerkorrektur** und **Fehlermitigation** sind deshalb entscheidend. 3. **Schaltkreisoptimierung**: Kompilieren der modularen Exponentiation und QFT erfordert clevere Optimierung, beispielsweise durch Variationsschaltungen oder Hybride aus Quanten- und klassischer Verarbeitung. Arbeiten zu **Fast Fourier Transformations** und **quantum arithmetic** versuchen, die Tiefe zu reduzieren. 4. **Alternativen zu RSA**: Auch wenn Shor RSA bricht, gibt es kryptographische Primitive, für die es bislang keine Quantenalgorithmen mit ähnlichem Durchbruch gibt (z. B. **sichere Hashfunktionen**). Die Erforschung neuer Quantenalgorithmen und die Bewertung ihrer Auswirkungen ist ein aktives Feld. ## Fazit Der Shor‑Algorithmus ist ein Paradebeispiel für den revolutionären Charakter der Quanteninformatik: Ein Problem, das der klassischen Welt eine massive Hürde bereitet, wird durch quantenmechanische Superposition und die QFT in polynomieller Zeit lösbar. Bisherige NISQ‑Demonstrationen zeigen, dass die periodische Struktur genutzt werden kann, auch wenn echte Faktorisierung großer Zahlen noch fern ist. Für Kryptografen ist Shor ein Weckruf: **Post‑Quantum‑Kryptografie** ist keine Option mehr, sondern eine Notwendigkeit. Für Quanteningenieure liefert Shor einen klaren Benchmark für die Skalierbarkeit von Hardware und Algorithmen. In Kombination mit anderen Algorithmen wie dem **Grover‑Algorithmus** (der quadratische Beschleunigung verspricht) und den Fortschritten in der **Quantenfehlerkorrektur**, bildet er einen Eckpfeiler der Quantenrevolution.