Umformung in das Problem der Ordnungsfindung

Zunächst wird das Faktorisierungsproblem in ein äquivalentes Problem umgeformt, das mit einem Quantenalgorithmus effizient gelöst werden kann.

1. Ist gerade, gib 2 als Faktor zurück.
2. Ist für ganze Zahlen und , gib als Faktor zurück.
3. Wähle zufällig ein zwischen und . Wenn der größte gemeinsame Teiler von und größer ist als 1, gib diese Zahl als Faktor zurück.
4. Finde mit Hilfe des Quantenalgorithmus zur Ordnungsfindung die kleinste ganze Zahl , so daß (also für eine ganze Zahl ). Diese Zahl ist die Ordnung von modulo .
5. Ist gerade und , so ist entweder oder ein Faktor von . Falls nicht, gehe zurück zu Schritt 3.

Mit Ausnahme von 4. können alle Schritte in ungefähr Schritten auf einem klassischen Computer durchgeführt werden. Zum Beweis der zahlentheoretischen Aussage von 5. s. [23.4]. Wie dort außerdem gezeigt wird, erfüllt mit der Wahrscheinlichkeit größer 1/2 die in 5. genannte Bedingung, so daß eine Endlosschleife zwischen 5. und 3. ausgeschlossen ist.