Shor-Algorithmus

1994 veröffentlichte der Mathematiker Peter Shor am MIT einen Algorithmus, der die Primfaktorzerlegung auf einem Quantencomputer in polynomialer Zeit löst. Auf klassischen Computern wächst die benötigte Zeit für dieses Problem exponentiell mit der Größe der Zahl. Genau darauf basiert die Sicherheit von RSA, dem weltweit meistgenutzten Verschlüsselungsverfahren.

RSA funktioniert so: Zwei große Primzahlen werden multipliziert. Das Ergebnis ist öffentlich (der Schlüssel), aber die Zerlegung zurück in die Faktoren ist für klassische Computer praktisch unmöglich, sofern die Zahlen groß genug sind (typisch: 2048 Bit, also Zahlen mit über 600 Stellen). Shors Algorithmus könnte diese Zerlegung in Stunden statt in Millionen von Jahren durchführen.

Der Haken: Für die Faktorisierung einer 2048-Bit-Zahl bräuchte man schätzungsweise 4.000 fehlerkorrigierte logische Qubits, was bei aktuellen Fehlerraten Millionen physischer Qubits erfordert. Stand 2025 ist kein Quantencomputer auch nur annähernd leistungsfähig genug. Trotzdem bereiten sich Regierungen und Unternehmen bereits vor: Das NIST hat 2024 die ersten post-quantenkryptografischen Standards verabschiedet.

In der Science Fiction hat Shors Algorithmus erstaunlich wenig Spuren hinterlassen, obwohl die Konsequenzen dramatisch wären: Eine Welt, in der alle bisherige Verschlüsselung über Nacht nutzlos wird.

Gerade weil der Shor-Algorithmus ein konkretes, alltägliches Fundament der digitalen Welt bedroht, ist er weit mehr als eine mathematische Kuriosität. Sollte je ein ausreichend großer Quantencomputer existieren, würde ein Großteil der heutigen Verschlüsselung schlagartig wertlos, von Bankverbindungen über Staatsgeheimnisse bis zur privaten Nachricht. Diese Aussicht treibt schon heute die Entwicklung quantensicherer Verfahren an, lange bevor die nötige Hardware überhaupt existiert. Der Shor-Algorithmus ist damit ein seltenes Beispiel dafür, dass eine rein theoretische Idee die reale Sicherheitsarchitektur einer ganzen Zivilisation in Bewegung setzt.