Problem der Primfaktorzerlegung

Für eine gegebene ganze Zahl sind zwei ganze Zahlen und gesucht, so daß gilt. Ein effizienter klassischer Algorithmus für diese Aufgabe ist nicht bekannt, insbesondere wenn und große Primzahlen sind, so daß die Faktorisierung von mehr als 200-stelligen Zahlen auf klassischen Computern praktisch unmöglich ist, weil alle Primzahlen bis überprüft werden müssen. Der Quanten-SHOR-Algorithmus [23.6] hingegen vermag die Faktorisierung in ungefähr Operationen zu vollziehen.