Shor-Algorithmus: Primfaktorzerlegung, RSA & PQC erklärt

Der Shor-Algorithmus ist ein Quantenalgorithmus zur Faktorisierung großer ganzer Zahlen sowie zur Berechnung diskreter Logarithmen. Er wurde 1994 vom Mathematiker Peter Shor entwickelt und löst die Primfaktorzerlegung in polynomieller Laufzeit bezogen auf die Bitlänge der Zahl. Die besten bekannten klassischen Faktorisierungsverfahren benötigen dagegen subexponentielle Laufzeit; ein klassischer Polynomialzeitalgorithmus für dieses Problem ist nicht bekannt. Kryptografisch relevante Schlüssellängen wie RSA-2048 bleiben damit für bekannte klassische Verfahren praktisch außer Reichweite.

Weil gängige asymmetrische Verschlüsselungsverfahren wie RSA auf der praktischen Schwierigkeit der Primfaktorzerlegung beruhen, gilt Shors Algorithmus als theoretischer Wendepunkt der modernen IT-Sicherheit. Heutige Quantencomputer können RSA-2048 mit Shors Algorithmus jedoch nicht brechen: Dafür fehlen ausreichend viele fehlerkorrigierte logische Qubits, zuverlässige Gatter und die nötige Laufzeitstabilität. Wie viele physische Qubits erforderlich wären, hängt stark von Architektur, physischer Fehlerrate und Fehlerkorrektur ab. Die Grundlagen zu Qubits, Superposition und Interferenz vermittelt der Leitfaden Technische Grundlagen; zentrale Fachbegriffe fasst das Quantencomputing-Glossar zusammen.

Warum Primfaktorisierung für moderne Verschlüsselung zentral ist

Zwei große Primzahlen miteinander zu multiplizieren, ist eine fundamentale mathematische Einbahnstraße: Das Produkt N = p · q lässt sich selbst von einfacher Hardware in Sekundenbruchteilen berechnen. Liegt jedoch nur die zusammengesetzte Zahl N (eine Semiprimzahl) vor, ist die Bestimmung der ursprünglichen Faktoren p und q ohne Vorwissen extrem zeitaufwendig.

Die besten bekannten klassischen Algorithmen – an erster Stelle das General Number Field Sieve (GNFS, Allgemeines Zahlkörpersieb) – weisen eine subexponentielle Laufzeit auf, die formal durch folgende Komplexitätsklasse beschrieben wird:

exp( O( (log N)1/3 · (log log N)2/3 ) )

Für eine Zahl mit 2048 Bit (wie bei Standard-RSA-Schlüsseln) bleibt die Faktorisierung mit den besten bekannten klassischen Verfahren praktisch außer Reichweite. Auf der Schwierigkeit der Faktorisierung beruht RSA. Diffie-Hellman und DSA beruhen dagegen auf diskreten Logarithmen in endlichen Körpern, ECDH und ECDSA auf diskreten Logarithmen auf elliptischen Kurven. Shors Algorithmus gefährdet beide Problemklassen.

Von der Faktorisierung zur Periodensuche: Das mathematische Fundament

Peter Shors entscheidender Durchbruch bestand darin, das algebraische Faktorisierungsproblem in ein Problem der Periodensuche (Ordnungsfindung) modularer Funktionen zu überführen. Das Verfahren nutzt zahlentheoretische Eigenschaften:

1. Zufallswahl: Wähle eine zufällige ganze Zahl a mit 1 < a < N und berechne den größten gemeinsamen Teiler ggT(a, N) mit dem klassischen Euklidischen Algorithmus. Ergibt ggT(a, N) > 1, ist bereits zufällig ein nichttrivialer Faktor gefunden.
2. Modulare Funktion: Ergibt ggT(a, N) = 1, betrachtet man die modulare Exponentialfunktion f(x) = ax mod N. Diese Funktion ist periodisch: Es existiert eine kleinste positive ganze Zahl r, sodass ar ≡ 1 (mod N) gilt. Diese Zahl r ist die sogenannte Ordnung von a modulo N.
3. Faktoren ableiten: Ist die gefundene Periode r eine gerade Zahl und gilt ar/2 ≢ -1 (mod N), so gilt:
   
   (ar/2 - 1)(ar/2 + 1) = ar - 1 ≡ 0 (mod N).
   
   Daraus liefern die beiden klassischen Berechnungen ggT(ar/2 - 1, N) und ggT(ar/2 + 1, N) mit hoher Wahrscheinlichkeit mindestens einen echten Primfaktor von N.
4. Wiederholung bei Bedarf: Ist r ungerade oder schlägt die Bedingung fehl, wird ein neues a gewählt. Nach wenigen Durchläufen gelingt die Zerlegung fast sicher.

Für allgemeine große Instanzen ist keine effiziente klassische Methode zur Ordnungsfindung bekannt. Der Quantencomputer bereitet eine Superposition vieler Exponenten x vor und nutzt Phaseninterferenz, um Informationen über die Periode mit hoher Wahrscheinlichkeit messbar zu machen.

Schritt-für-Schritt: Ablauf des Shor-Algorithmus

Der vollständige Shor-Algorithmus ist ein Hybridverfahren, das Quantenroutinen und klassische Nachverarbeitung kombiniert:

1. Register initialisieren: Es werden zwei Quantenregister vorbereitet. Das erste Register (Eingangsregister) benötigt t ≈ 2 · log2(N) Qubits, um ausreichend Zustände für eine präzise Fourier-Analyse abzubilden. Das zweite Register (Ausgangsregister) umfasst n = log2(N) Qubits zur Speicherung des Funktionswerts.
2. Gleichmäßige Superposition erzeugen: Durch Anwendung von Hadamard-Gattern auf alle Qubits des ersten Registers entsteht eine gleichmäßige Überlagerung aller möglichen Zustände von |0⟩ bis |2t - 1⟩.
3. Modulare Exponentiation im Quantenraum: Eine reversible Quantenschaltung berechnet die Funktion |x⟩|0⟩ → |x⟩|ax mod N⟩. Dabei werden Eingabe- und Ausgangsregister quantenmechanisch korreliert und im Allgemeinen verschränkt. Dieser Schritt ist gattertechnisch der anspruchsvollste Teil des Algorithmus.
4. Messung des zweiten Registers: Wird das zweite Register gemessen, kollabiert es auf einen konkreten Funktionswert y0. Das erste Register verbleibt dadurch in einer periodischen Superposition genau jener Werte x, für die ax mod N = y0 gilt – mit exaktem Schrittabstand der gesuchten Periode r.
5. Quanten-Fourier-Transformation (QFT): Nun wird auf das erste Register die Quanten-Fourier-Transformation angewendet. Sie konzentriert die Messwahrscheinlichkeit auf Werte nahe j · 2t / r. Exakte Spitzen an ganzzahligen Vielfachen entstehen nur in passenden Teilbarkeitsfällen; allgemein liefert die Messung eine Näherung, aus der die Periode rekonstruiert wird.
6. Messung und klassische Rekonstruktion: Das erste Register wird ausgelesen und liefert einen Wert m. Das Verhältnis m / 2t stellt eine rationale Näherung für j / r dar. Die Kettenbruchentwicklung (Continued Fraction Expansion) liefert daraus einen Kandidaten für r. Dieser wird klassisch geprüft; liefert er nur einen Teiler der Periode oder erfüllt er die Bedingungen nicht, sind weitere Messungen beziehungsweise Durchläufe nötig.

Die theoretische Gesamtlaufzeit liegt mit elementarer Arithmetik in der Größenordnung von O((log N)3). Shors ursprüngliche Analyse nennt mit schneller Multiplikation O((log N)2 · log log N · log log log N). Damit ist der Quantenalgorithmus polynomial; gegenüber dem subexponentiellen klassischen GNFS ergibt sich nach heutigem Kenntnisstand ein superpolynomieller asymptotischer Vorteil.

Komplexität und Hardwarebedarf: Wie viele Qubits braucht Shor?

Eine bekannte platzsparende Schaltkreis-Konstruktion nach Beauregard kommt für eine n-Bit-Zahl mit rund 2n + 3 logischen Qubits aus. Für einen 2048-Bit-RSA-Schlüssel entspräche das in diesem Modell rund 4.100 perfekten logischen Qubits. Andere Schaltkreis- und Architekturentscheidungen verschieben jedoch den Bedarf an Qubits, Gattern und Laufzeit.

In der physikalischen Realität operieren heutige Systeme jedoch in der sogenannten NISQ-Ära (Noisy Intermediate-Scale Quantum): Physische Qubits sind anfällig für Rauschen, Dekohärenz und Gatterfehler. Wie viele physische Qubits ein stabiles logisches Qubit benötigt, ist kein fester Umrechnungsfaktor. Der Overhead hängt unter anderem von physischer Fehlerrate, Ziel-Fehlerrate, Fehlerkorrekturcode, Gattergeschwindigkeit und Architektur ab.

Ressourcenschätzungen sind deshalb Momentaufnahmen unter konkreten Annahmen: Gidney und Ekerå (2021) schätzten für RSA-2048 rund 20 Millionen physische Qubits bei etwa acht Stunden Laufzeit und ungefähr 2,6 Milliarden Toffoli-Gattern. Ein Preprint von Gidney aus dem Jahr 2025 kommt mit veränderten Verfahren und Annahmen auf weniger als eine Million physische Qubits bei weniger als einer Woche Laufzeit. Diese Zahlen sind keine Prognosen für ein konkretes Gerät, sondern verdeutlichen die starke Abhängigkeit vom Fehlermodell und Schaltungsdesign. Welche Ansätze die Industrie bei Supraleitern, Ionenfallen und photonischen Systemen verfolgt, analysiert der Technologie & Hardware Hub.

Experimentelle Demonstrationen: Was wurde bisher faktorisiert?

Seit Peter Shors Entdeckung haben Forschungsinstitute und Technologiekonzerne den Algorithmus schrittweise auf experimenteller Quantenhardware demonstriert:

• 2001 (IBM & Stanford): Bei einer frühen Demonstration wurde die Zahl 15 mit einem 7-Qubit-NMR-System in die Primfaktoren 3 und 5 zerlegt.
• 2012 (Universität Bristol): Ein photonischer Quantenprozessor demonstrierte eine kompilierte Faktorisierung der Zahl 21.
• 2019 (Amico, Saleem & Kumph): Die Forscher führten kompilierte Shor-Varianten für 15, 21 und 35 auf dem 16-Qubit-Prozessor ibmqx5 aus und nutzten dafür fünf, sechs beziehungsweise sieben Qubits.

Die hier genannten Demonstrationen nutzen stark vereinfachte Versuchsaufbauten („compiled Shor“), bei denen Vorwissen über die Zielzahlen in die Schaltkreisoptimierung einfließt. Sie zeigen einzelne Bausteine und Prinzipien, sind aber nicht mit einer allgemeinen Faktorisierung unbekannter 2048-Bit-Zahlen vergleichbar.

Auswirkungen auf die IT-Sicherheit & Post-Quantum-Kryptografie

Obwohl praktische Angriffe auf 2048-Bit-Schlüssel noch Jahre entfernt sind, zwingt der Shor-Algorithmus Staat und Wirtschaft bereits heute zum Handeln. Der Grund liegt im sogenannten „Harvest Now, Decrypt Later“-Prinzip: Geheimdienste und Angreifer schneiden verschlüsselten Datenverkehr schon heute massenhaft mit, speichern ihn ab und warten darauf, die Schlüssel in Zukunft mit einem fehlertoleranten Quantencomputer nachträglich zu brechen.

Vom Shor-Algorithmus betroffen sind alle gängigen Public-Key-Verfahren:

• RSA: Basiert auf Primfaktorisierung.
• Diffie-Hellman & DSA: Basieren auf dem diskreten Logarithmus über endlichen Körpern.
• ECDSA & ECDH: Basieren auf dem diskreten Logarithmus auf elliptischen Kurven.

Symmetrische Verschlüsselungen wie AES und kryptografische Hashfunktionen wie SHA-256 werden durch Shors Algorithmus nicht direkt angegriffen. Der Grover-Algorithmus reduziert im idealisierten Modell die Abfragekomplexität einer generischen Schlüssel- oder Urbildsuche quadratisch. AES-256 bietet dabei grob ein mit klassischer 128-Bit-Schlüsselsuche vergleichbares Sicherheitsniveau; das ist jedoch keine Aussage über sämtliche denkbaren Quantenangriffe oder über Hashkollisionen.

Die globale Sicherheitsarchitektur stellt deshalb auf quantenresistente Verschlüsselung um. Welche Algorithmen (z. B. ML-KEM und ML-DSA) vom US-Standardisierungsinstitut NIST freigegeben wurden und wie Migrationen ablaufen, vertieft unser Spezialbeitrag zur Post-Quantum-Kryptografie (PQC). Einen umfassenden Gesamtüberblick über alle industriellen Einsatzfelder bietet zudem der Hub Anwendungen von Quantencomputern.

Häufige Fragen zum Shor-Algorithmus

Was ist der Shor-Algorithmus einfach erklärt?

Der Shor-Algorithmus ist eine Rechenanleitung für Quantencomputer, um große Zahlen in ihre Primfaktoren zu zerlegen. Die besten bekannten klassischen Verfahren skalieren dafür subexponentiell; Shor nutzt quantenmechanische Superposition und Interferenz, um das Problem in polynomieller Zeit zu lösen.

Kann der Shor-Algorithmus heute schon RSA-2048 knacken?

Nein. Heutige Quantenprozessoren verfügen nicht über die dafür nötige Zahl ausreichend stabiler logischer Qubits und zuverlässiger Gatter. Schätzungen für RSA-2048 reichen – abhängig von Fehlerrate, Architektur, Fehlerkorrektur und Laufzeit – von weniger als einer Million bis zu mehreren zehn Millionen physischen Qubits.

Welche Verschlüsselungsverfahren sind durch Shor gefährdet?

Gefährdet sind nahezu alle heute im Internet eingesetzten asymmetrischen Verfahren: RSA, ECC (Elliptic Curve Cryptography) sowie Diffie-Hellman-Schlüsselaustausche. Symmetrische Verschlüsselungsverfahren wie AES-256 gelten bei ausreichender Schlüssellänge weiterhin als sicher.

Was ist der Unterschied zwischen dem Shor- und dem Grover-Algorithmus?

Shors Algorithmus nutzt Periodenfindung und bietet für Faktorisierung gegenüber den besten bekannten klassischen Verfahren einen superpolynomiellen asymptotischen Vorteil. Grovers Algorithmus beschleunigt die unstrukturierte Suche im idealisierten Abfragemodell quadratisch.

Fazit & Ausblick

Der Shor-Algorithmus zeigt, dass Faktorisierung und diskrete Logarithmen auf einem fehlertoleranten Quantencomputer in Polynomialzeit lösbar wären. Ein entsprechend effizienter klassischer Algorithmus ist nicht bekannt; ein Beweis, dass kein solcher klassischer Algorithmus existieren kann, liegt jedoch ebenfalls nicht vor. Auch wenn der praktische Bruch heutiger Kryptostandards noch an der Hardware-Skalierung scheitert, ist die weltweite Umstellung auf Post-Quantum-Kryptografie bereits in vollem Gange. Für die Beurteilung von Hardwarereife und Zeitplänen bleibt Shors Algorithmus ein zentraler Härtetest für zukünftige, fehlertolerante Quantenrechner.

Weiterführende Einordnung: Welche wirtschaftlichen Chancen und Risiken sich aus der Hardware-Entwicklung für Unternehmen und Märkte ergeben, ordnet unser Fachartikel zu Quantencomputer Aktien & Investments sachlich ein.

Quellen und weiterführende Forschung

• Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (SIAM J. Comput. 26, 1997).
• Lenstra & Lenstra (Hrsg.): The Development of the Number Field Sieve (Springer, 1993) – Grundlage zur subexponentiellen GNFS-Komplexität.
• Stéphane Beauregard: Circuit for Shor’s algorithm using 2n+3 qubits (Quantum Information & Computation 3, 2003).
• Vandersypen et al.: Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance (Nature 414, 2001).
• Martín-López et al.: Experimental realization of Shor’s quantum factoring algorithm using qubit recycling (Nature Photonics 6, 2012).
• Amico, Saleem & Kumph: Experimental study of Shor’s factoring algorithm using the IBM Q Experience (Physical Review A 100, 2019).
• Gidney & Ekerå: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (Quantum 5, 2021).
• Craig Gidney: How to factor 2048 bit RSA integers with less than a million noisy qubits (Preprint, 2025).
• Lov K. Grover: A fast quantum mechanical algorithm for database search (STOC, 1996).
• NIST: Report on Post-Quantum Cryptography (NISTIR 8105).