next up previous contents
Nächste Seite: Wahrscheinlichkeit für erfolgreiche Reduktion Aufwärts: Reduktion der Faktorisierung auf Vorherige Seite: Reduktion der Faktorisierung auf   Inhalt

Vorgehensweise

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

\begin{displaymath}
x^r \equiv 1 \bmod n.
\end{displaymath} (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

\begin{displaymath}
(x^{r/2} - 1)(x^{r/2} + 1) = x^r - 1 \equiv 0 \bmod n
\end{displaymath} (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

\begin{displaymath}
x^2 \equiv 1 \bmod n
\end{displaymath} (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:
$\displaystyle x_1$ $\textstyle \equiv$ $\displaystyle \ \ \, 1 \bmod p$ (4)
$\displaystyle x_1$ $\textstyle \equiv$ $\displaystyle \ \ \, 1 \bmod q$  
$\displaystyle x_2$ $\textstyle \equiv$ $\displaystyle -1 \bmod p$ (5)
$\displaystyle x_2$ $\textstyle \equiv$ $\displaystyle -1 \bmod q$  
$\displaystyle x_3$ $\textstyle \equiv$ $\displaystyle \ \ \, 1 \bmod p$ (6)
$\displaystyle x_3$ $\textstyle \equiv$ $\displaystyle -1 \bmod q$  
$\displaystyle x_4$ $\textstyle \equiv$ $\displaystyle -1 \bmod p$ (7)
$\displaystyle x_4$ $\textstyle \equiv$ $\displaystyle \ \ \, 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$.


next up previous contents
Nächste Seite: Wahrscheinlichkeit für erfolgreiche Reduktion Aufwärts: Reduktion der Faktorisierung auf Vorherige Seite: Reduktion der Faktorisierung auf   Inhalt
Stefan Röhrich stefan@roehri.ch
1999-11-27 19:52:04