Comment:
Shor-Algorithmus (Schritt 3 ist der Quantencomputer-Schritt).
Eingabe: Eine zusammengesetzte Zahl n.
1. Waehle eine Zahl x (1 < x < n).
2. Bestimme den ggT(x, n) (z. B. mittels des Euklidischen Algorithmus).
Falls das Ergebnis ungleich 1 ist, gib dies als Loesung zurueck und terminiere.
Sonst fahre mit dem naechsten Schritt fort.
3. Bestimme mit Hilfe des Quantenteils (s. u.) die Ordnung r von x
in der primen Restklassengruppe (\mathbb Z/n\mathbb Z)^\times
(das kleinste r\in\mathbb{N}, so dass x^r\equiv 1 (\textrm{mod} n)).
Schritt 2 stellte sicher, dass ein solches r existiert.
(congmod-inverse-smallest, das r das kleinste ist, ist irrelevant).
4. Beginne erneut bei 1, falls:
r ungerade ist, oder
x^{r/2}\equiv -1 (\textrm{mod} n).
5. Gib \textrm{ggT}(x^{r/2} - 1, n) als Loesung zurueck.
Warum ist der Wert in Schritt 5 eine Loesung? -
Betrachte das Produkt (x^{r/2}-1 ) * (x^{r/2} +1 ) = x^r -1 .
Wir wissen nach Schritt 3, dass gilt: x^r -1 ≡ 0 mod n, dass nicht gilt: x^{r/2}+1 ≡ 0 mod n (Schritt 4)
und dass nicht gilt: x^{r/2}-1 ≡ 0 mod n (Schritt 3, da r die kleinste Zahl mit x^r -1 ≡ 0 mod n ist und {r/2} < r gilt),
woraus folgt, dass x^{r/2} -1 nichttriviale Teiler von n enthaelt,
der euklidische Algorithmus zur Berechnung des ggT liefert diese Teiler in Polynomialzeit.