⚛️ Shors Algorithmus

Es ist die kleinste positive ganze Zahl r, sodass aʳ mod N = 1 gilt. Da aˣ mod N mit der Periode r zyklisch verläuft, können Sie, sobald Sie r kennen, damit Faktoren von N algebraisch extrahieren — diese Simulation hebt diesen wiederkehrenden Zyklus direkt im Balkendiagramm hervor.

Die Periode von aˣ mod N klassisch zu finden, erfordert das Prüfen der Werte einzeln, was für große N exponentiell langsam wird. Ein Quantencomputer kann eine Überlagerung über alle x gleichzeitig vorbereiten und mit der QFT Messergebnisse bei Vielfachen von Q/r konzentrieren, wodurch r in weit weniger Schritten offenbart wird.

Stellt sich heraus, dass die Periode r ungerade ist, oder ist a^(r/2) ≡ −1 (mod N), kann der ggT-Schritt aus dieser bestimmten Wahl von a keinen nichttrivialen Faktor extrahieren — die Lösung besteht einfach darin, eine andere Basis a zu wählen und es erneut zu versuchen, weshalb die Schaltfläche „Zufällige a" nach einer wahrscheinlich funktionierenden sucht.

Die Sicherheit von RSA beruht darauf, dass es rechnerisch nicht durchführbar ist, das große Produkt zweier als öffentlicher Schlüssel verwendeter Primzahlen zu faktorisieren. Shors Algorithmus faktorisiert ganze Zahlen exponentiell schneller als die besten bekannten klassischen Algorithmen, sodass ein ausreichend großer Quantencomputer, der ihn ausführt, derzeit sichere RSA-Schlüssel brechen könnte.

Sobald r gerade ist und a^(r/2) nicht ≡ −1 mod N ist, bedeutet die Identität (a^(r/2)−1)(a^(r/2)+1) ≡ 0 (mod N), dass N einen nichttrivialen gemeinsamen Faktor mit mindestens einem dieser beiden Terme teilen muss — die Berechnung des ggT für jeden zieht diesen gemeinsamen Faktor direkt heraus.