Begriff
Shor's Algorithm
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Unsere Sicherheit (Online-Banking, HTTPS) basiert auf RSA. RSA basiert darauf, dass es schwer ist, eine riesige Zahl ($N = p \cdot q$) in ihre Teiler p und q zu zerlegen (Faktorisierung). Ein klassischer Supercomputer braucht dafür Jahrmillionen. Peter Shor entdeckte 1994: Ein Quantencomputer kann das in Minuten. Der Algorithmus nutzt Quanten-Interferenz, um "falsche" Teiler auszulöschen und den "richtigen" Teiler zu verstärken. Das war der Moment, als die Welt merkte: "Quantencomputer sind nicht nur Spielzeug."
Merksatz: Ein Quantenalgorithmus zur Faktorisierung ganzer Zahlen, der exponentiell schneller ist als der beste bekannte klassische Algorithmus und theoretisch die RSA-Verschlüsselung brechen kann.
Gar nicht (noch). Der größte Shor-Lauf bisher faktorisierte die Zahl 15 (in 3 und 5). Vielleicht auch 21. Um RSA-2048 zu knacken, bräuchte man Millionen fehlerfreier Qubits. Wir haben aktuell ~100-1000 noisy Qubits. Aber wir bereiten uns vor: Post-Quantum Cryptography (PQC) entwickelt Algorithmen (wie Kyber/Dilithium), die auch gegen Shor immun sind.
1. Period Finding
Das Kernproblem ist nicht Faktorisierung, sondern Periodensuche. Funktion $f(x) = a^x \mod N$. Diese Funktion wiederholt sich (periodisch). Wenn man die Periode $r$ findet, kann man (mit Euler's Theorem) die Faktoren von N berechnen. Periodensuche ist klassisch schwer. Quantenmechanisch einfach (mit QFT).
2. Hybrid Approach
Shor ist hybrid.
- Klassisch: Wähle Zufallszahl $a$. (Einfach).
- Quanten: Finde Periode von $f(x) = a^x \mod N$. (Der QFT-Magie-Teil).
- Klassisch: Berechne Teiler aus der Periode. (Einfach, ggT).
1. Continued Fractions (Kettenbrüche)
Nachdem die Quanten-Hardware (QFT) uns einen Messwert geliefert hat, haben wir nur einen Schätzwert für die Phase $s/r$.
Wir wissen aber nicht, was $r$ (die Periode) ist.
Hier kommt klassische Mathematik ins Spiel: Der Kettenbruch-Algorithmus.
Er findet die "beste rationale Näherung" für den Messwert. Wenn die Hardware misst 0.1428..., erkennt der Algorithmus: "Das ist $1/7$". Wir folgern: $r=7$ (die Periode). Dies zeigt: Erstaunlich viel Arbeit bei Quanten-Algorithmen ist eigentlich klassische Nachbearbeitung.
2. Space-Time Complexity & Modulo-Exponentiation
Der schwierigste Teil im Quantencomputer ist nicht die QFT, sondern die modulare Exponentiation ($a^x \mod N$). Dafür braucht man viele logische Gatter.
- Space: Man braucht ca. $2n$ Qubits für eine $n$-Bit Zahl.
- Time: Man braucht $O(n^3)$ Gatter. Um eine RSA-2048 Zahl zu knacken, bräuchte man 4096 logische Qubits (was Millionen physischer Qubits entspricht). Es gibt Optimierungen (z.B. Beauregard's Algorithmus), die mit weniger Qubits auskommen, aber dann deutlich länger brauchen. Experten optimieren hier um jedes einzelne Qubit, da Qubits aktuell die teuerste Ressource der Welt sind.
3. Reversibility & Garbage Collection
Da Quantencomputer unitär (reversibel) arbeiten, muss jeder Schritt der Rechnung (auch Hilfsberechnungen wie Addition) rückgängig gemacht werden können. Wenn man während der Exponentiation Zwischenwerte erzeugt ("Garbage"), darf man sie nicht einfach löschen (das würde die Verschränkung stören). Man muss sie Un-compute-n, also die Rechnung rückwärts laufen lassen. Das verdoppelt den Aufwand für Shor fast, ist aber physikalisch zwingend notwendig.
Quick-Check
Knackt es auch AES?
Nein. Shor knackt nur asymmetrische Krypto (RSA, ECC), die auf Zahlentheorie basiert. Symmetrische Krypto (AES) wird durch Glovers Algorithmus nur "halbiert" (AES-128 wird zu AES-64), aber nicht gebrochen.Wann ist es soweit?
Schätzung: 10 bis 30 Jahre. Das nennt man "Y2Q" (Years to Quantum).Peter Shor?
Mathematiker bei AT&T Bell Labs (damals). Er erfand auch Quanten-Fehlerkorrektur.