Vorgehensweise

Die Ordnung $r$ eines Elementes $x \in \mathbbm{Z}_n$ ist die kleinste natürliche Zahl, so daß

$$x^r \equiv 1 \bmod n.$$ (1)

Die Faktorisierung von $n$ wird nach Miller wie nachfolgend aufgeführt auf die Bestimmung der Ordnung zurückgeführt. Zunächst seien $n = p q$, $p, q \neq 2$ und Primzahlen (ansonsten schrittweise Vorgehensweise, falls $n = p_1 \cdotp \ldots \cdotp p_k$).

Zuerst bestimmt man die Ordnung $r$ eines zufällig gewählten $x$ ( $\in \{2, \ldots, n-1\}$). 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 $n$ durch $p = {\mathrm{ggT}}(x^{r/2} - 1, n)$ und $q = {\mathrm{ggT}}(x^{r/2} + 1, n)$, denn

$$(x^{r/2} - 1)(x^{r/2} + 1) = x^r - 1 \equiv 0 \bmod n$$ (2)

Falls $r$ ungerade (dann ist $x^{r/2}$ undefiniert) oder $x^{r/2} \equiv -1 \bmod n$ (es ergeben sich die trivialen Faktoren als Lösung) ist, funktioniert diese Methode allerdings offensichtlich nicht, man muß es dann erneut mit einem anderen $x$ versuchen.

Daß man solche Zahlen findet, kann man sich auch so verdeutlichen:

Die Gleichung

$$x^2 \equiv 1 \bmod n$$ (3)

hat immer die trivialen Lösungen $x \equiv \pm 1 \bmod n$. Wenn $n$ eine Primzahl ist, dann sind dies die einzigen Lösungen, anderenfalls gibt es weitere Lösungen. Betrachten wir dazu folgende Gleichungen:

$$x_1 \equiv \ \ \, 1 \bmod p$$ (4)

$$x_1 \equiv \ \ \, 1 \bmod q$$

$$x_2 \equiv -1 \bmod p$$ (5)

$$x_2 \equiv -1 \bmod q$$

$$x_3 \equiv \ \ \, 1 \bmod p$$ (6)

$$x_3 \equiv -1 \bmod q$$

$$x_4 \equiv -1 \bmod p$$ (7)

$$x_4 \equiv \ \ \, 1 \bmod q .$$

In jedem Fall ist $x_i^2 \equiv 1 \bmod p$ und $\bmod\ q$, so daß (3) erfüllt ist. Nach dem Chinesischen Restsatz ([DW95]) hat jede dieser Gleichungen eine eindeutige Lösung $\bmod\ n$ und wir erhalten aus den beiden letzten Gleichungen $x_3 = a$ und $x_4 = -a \bmod n$ ein Paar nichttrivialer Lösungen. So ist $(a+1)(a-1) \equiv 0 \bmod n$ und $a\pm1 \neq 0$ und somit teilt $n$ $(a+1)(a-1)$ aber nicht $a\pm1$ und der größte gemeinsame Teiler von $n$ und $a\pm1$ ist ein nichttrivialer Faktor von $n$.