Startseite▸Quantencomputing▸Shors Algorithmus — Quantenfaktorisierung durch Periodensuche

🔢 Shors Algorithmus — Quantenfaktorisierung durch Periodensuche

Interaktiver Shors-Algorithmus-Simulator: Finden Sie die Periode r von a^x mod N, betrachten Sie eine illustrative Quantenspektrum-Visualisierung und ermitteln Sie N's Primfaktoren über den euklidischen Algorithmus.

Quantencomputing2DFortgeschritten60 FPS

Über Shors Algorithmus

Shors Algorithmus, 1994 vom Mathematiker Peter Shor veröffentlicht, ist das Ergebnis, das Quantencomputing von einer theoretischen Kuriosität zu einer existenziellen Frage für die moderne Kryptografie machte. Er faktorisiert eine zusammengesetzte ganze Zahl N, indem er die Periode r der Folge ȧ mod N für eine zu N teilerfremde Basis a findet — eine Aufgabe, die ein Quantencomputer exponentiell schneller ausführen kann als jede bekannte klassische Methode, unter Verwendung einer Operation namens Quantenphasenschätzung (QPE), um r direkt aus Interferenzmustern in einer Überlagerung von Zuständen abzulesen. Ist r einmal bekannt, offenbart eine kurze Berechnung mit dem euklidischen Algorithmus, angewandt auf a^r/2 ± 1 und N, sehr häufig zwei echte, nichttriviale Faktoren von N.

Das ist weit über die reine Mathematik hinaus von Bedeutung: Das RSA-Public-Key-Kryptosystem, das noch immer einen großen Teil des Internetverkehrs, des Bankwesens und der sicheren Kommunikation absichert, beruht vollständig auf der Annahme, dass die Faktorisierung großer Zahlen rechnerisch nicht durchführbar ist. Ein ausreichend großer, fehlertoleranter Quantencomputer, der Shors Algorithmus ausführt, würde diese Annahme zunichtemachen, weshalb Regierungen und Normungsgremien bereits post-quantenkryptografische Verfahren einführen, die gegen Quantenangriffe resistent sein sollen. Dieser Simulator führt durch die klassische Periodensuche-Sequenz, eine illustrative Nachbildung des Quantenspektrums, das QPE messen würde, und die echte Arithmetik des euklidischen Algorithmus, die aus einer Periode eine Faktorisierung macht — anhand der kleinen, von Hand nachprüfbaren Beispiele N = 15, 21 und 35.

Häufig gestellte Fragen

Welches Problem löst Shors Algorithmus eigentlich?

Er faktorisiert eine zusammengesetzte ganze Zahl N in ihre Primfaktoren. Klassisch benötigen die besten bekannten Algorithmen zur Faktorisierung großer Zahlen eine Zeit, die fast exponentiell mit der Anzahl der Stellen wächst, weshalb die RSA-Verschlüsselung, die auf der Schwierigkeit der Faktorisierung beruht, jahrzehntelang sicher geblieben ist. Shors Algorithmus faktorisiert N in einer Zeit, die nur polynomiell wächst — für ausreichend große N eine exponentielle Beschleunigung.

Warum hilft das Finden einer Periode r, N zu faktorisieren?

Ist a teilerfremd zu N und r gerade, wobei a^r/2 nicht kongruent zu −1 modulo N ist, dann sind a^r/2 − 1 und a^r/2 + 1 Zeugen dafür, dass N ihr Produkt, aber keinen der beiden Faktoren allein teilt. Der euklidische Algorithmus, angewandt auf ggT(a^r/2 − 1, N) und ggT(a^r/2 + 1, N), extrahiert dann direkt aus dieser arithmetischen Tatsache einen echten, nichttrivialen Faktor von N.

Führt dieser Simulator eine echte Quantenberechnung aus?

Nein, und diese Seite sagt das ausdrücklich. Die Simulation der eigentlichen Quantenphasenschätzungsschaltung, die r findet, würde die Modellierung vieler Qubits erfordern, was weit über das hinausgeht, was ein Browser-Canvas sinnvoll darstellen kann. Stattdessen berechnet diese Demo r klassisch mit einer gewöhnlichen Schleife und zeichnet dann ein illustratives „Spektrum" mit Spitzen bei k/r, um zu Lehrzwecken darzustellen, wie eine echte QPE-Messung aussehen würde.

Warum schlägt der Periodensuche-Trick manchmal fehl?

Die ggT-Konstruktion funktioniert nur, wenn die Periode r gerade ist und a^r/2 nicht kongruent zu −1 modulo N ist. Stellt sich r als ungerade heraus, oder liefert die ggT-Berechnung nur die trivialen Faktoren 1 oder N, funktioniert die gewählte Basis a für diese Methode einfach nicht. Die übliche Lösung, sowohl hier als auch im echten Algorithmus, besteht darin, eine andere zufällige Basis a zu versuchen und zu wiederholen.

⚙ Unter der Haube

QuantencomputingZahlentheorieKryptografieCanvas 2DPeriodensuche

2D · HTML5 Canvas 2D · 60 FPS Ziel · läuft vollständig clientseitig, keine Installation nötig