Wahrscheinlichkeit für erfolgreiche Reduktion

Die Wahrscheinlichkeit, daß $r$ ungerade oder $x^{r/2} \equiv -1 \bmod n$ ist, also daß mittels der Reduktion für ein $x$ keine nichttrivialen Faktoren ermittelt werden können, ist kleiner $1/2$ (bzw. $1/2^{k-1}$ mit $k$ als Anzahl der unterschiedlichen ungeraden Primfaktoren von $n$).

Seien $p$ und $q$ die Primfaktoren von $n$ und $r_p =: 2^i u$ die Ordnung von $x \bmod p$ bzw. $r_q =: 2^j v$ von $x \bmod q$ (mit i, j maximal), damit ist $r \equiv {\mathrm kgV}(r_p, r_q) \bmod n$.

Der Algorithmus funktioniert nicht, falls $i = j$, denn dann ist entweder $r$ ungerade ($i = j = 0$) oder $x^{r_p/2} \equiv -1 \bmod p$ und $x^{r_q/2} \equiv -1 \bmod q$ ($\mathbbm{Z}_p$ bzw. $\mathbbm{Z}_q$ sind zyklische Gruppen), so daß $x^{r} \equiv -1 \bmod n$.

Nach dem Chinesischen Restsatz können wir anstatt $x$ zu wählen auch $x_p$ und $x_q$ wählen, so daß $x$ sich aus $x \equiv x_p \bmod p$ und $x \equiv x_q \bmod q$ ergibt. Da $p$ und $q$ Primzahlen sind, sind die multiplikativen Gruppen $\bmod\ p$ bzw. $\bmod\ q$ zyklisch, so daß P$(i=j) < 1/2$.

Diese Argumentation funktioniert analog, falls $n = p_1 \cdotp \ldots \cdotp p_k$.