Shor-Algorithmus
Faktorisiert große Zahlen in polynomieller Zeit — und macht damit RSA und elliptische Kurven unbrauchbar, sobald die passende Hardware existiert.
Peter Shor veröffentlichte den Algorithmus 1994 bei den Bell Labs. Es war der erste überzeugende Beweis dafür, dass Quantencomputer ein praktisch relevantes Problem exponentiell schneller lösen können als jede bekannte klassische Methode, und er machte aus einer theoretischen Kuriosität ein Feld, das Regierungen finanzieren.
Der Kerngedanke ist unerwartet: Faktorisierung wird umformuliert als Suche nach der Periode einer Funktion, und genau darin ist die Quanten-Fourier-Transformation stark. RSA-2048 zu brechen erfordert Schätzungen zufolge einige Tausend fehlerkorrigierte logische Qubits, also Millionen physische — weit jenseits heutiger Maschinen, aber nah genug, dass die Migration zu Post-Quanten-Kryptografie bereits läuft.