Die Ordnung eines Elementes
ist die kleinste
natürliche Zahl, so daß
(1) |
Die Faktorisierung von wird nach Miller wie nachfolgend aufgeführt auf die Bestimmung der Ordnung zurückgeführt. Zunächst seien , und Primzahlen (ansonsten schrittweise Vorgehensweise, falls ).
Zuerst bestimmt man die Ordnung eines zufällig gewählten ( ). Dies ist (bis jetzt) klassisch nicht effizient möglich und hierzu wird auch bei Shors Algorithmus der Quantencomputer verwendet.
Nun erhält man die Primfaktoren von durch
und
,
denn
(2) |
Falls ungerade (dann ist undefiniert) oder (es ergeben sich die trivialen Faktoren als Lösung) ist, funktioniert diese Methode allerdings offensichtlich nicht, man muß es dann erneut mit einem anderen versuchen.
Daß man solche Zahlen findet, kann man sich auch so verdeutlichen:
Die Gleichung
(4) | |||
(5) | |||
(6) | |||
(7) | |||
In jedem Fall ist und , so daß (3) erfüllt ist. Nach dem Chinesischen Restsatz ([DW95]) hat jede dieser Gleichungen eine eindeutige Lösung und wir erhalten aus den beiden letzten Gleichungen und ein Paar nichttrivialer Lösungen. So ist und und somit teilt aber nicht und der größte gemeinsame Teiler von und ist ein nichttrivialer Faktor von .