Quelltext der Seite Pollard-Rho-Methode

[[Datei:Pollard Rho.png|mini|150px|Grafische Darstellung der Teilergebnisse]]
Die '''Pollard-Rho-Methoden''' sind [[Algorithmus|Algorithmen]] zur Bestimmung der Periodenlänge einer Zahlenfolge, die mit einer mathematischen Funktion berechnet wird. Verschiedene schwierige mathematische Probleme wie der [[Diskreter Logarithmus|diskrete Logarithmus]] und die [[Faktorisierungsverfahren|Faktorisierung]] lassen sich mit diesen Methoden berechnen. Eine optimierte Variante der Pollard-Rho-Methode wurde von [[John M. Pollard]] im Jahre [[1975]] zur [[Primfaktorzerlegung]] entwickelt. Derartige Verfahren lassen sich auch zur Berechnung von [[Kollisionssicherheit|Kollisionen]] in Hash-Funktionen anwenden.

Bei den Pollard-Rho-Methoden werden Folgen von Teilergebnissen berechnet. Ab einem bestimmten Punkt wiederholt sich ein Teil dieser Teilergebnisse nur noch. Man kann die Teilergebnisse grafisch so anordnen, dass sich die Gestalt des Buchstaben [[Rho|ρ]] (Rho) erkennen lässt. Daraus leitet sich die Bezeichnung der Methoden ab.

== Funktionsweise ==

Gesucht ist ein echter Teiler <math>p</math> der Zahl <math>n</math>. Im Allgemeinen muss dieser Teiler jedoch nicht zwingend eine [[Primzahl]] sein. Das Verfahren beruht auf der Erzeugung einer Folge von [[Pseudozufallszahlen]]. Zur Erstellung der Zufallsfolge kann eine relativ beliebige Funktion <math>f \colon \N \to \N </math> verwendet werden. Es ist lediglich erforderlich, dass aus <math>x\equiv y\pmod p</math> auch <math>f(x)\equiv f(y)\pmod p</math> folgt, und dies gilt beispielsweise bereits, wenn <math>f</math> durch ein [[Polynom]] mit ganzzahligen Koeffizienten gegeben ist.

Die Folge startet mit einem weitgehend beliebig wählbaren Startwert <math>x_0</math>. Die weiteren Werte werden iterativ berechnet gemäß
:<math>x_i = f(x_{i-1})</math>
Die Funktionswerte [[modulo]] <math>p</math> können maximal die <math>p</math> verschiedenen Werte <math>0, 1, 2, \ldots , p- 1</math> annehmen. Tritt einer dieser Werte erneut auf, so wiederholen sich anschließend diese Werte modulo <math>p</math>. Dies geschieht spätestens nach <math>p</math> Iterationen und im Mittel nach etwa <math>\sqrt p</math> Iterationen. Aus denselben Gründen kann man nach etwa <math>\sqrt n</math> Iterationen erwarten, dass sich die Werte modulo <math>n</math> wiederholen. Wenn bereits bekannt ist, dass <math>n</math> einen kleinen Primfaktor hat, ist <math>\sqrt p</math> erheblich kleiner als <math>\sqrt n</math>, so dass gehofft werden darf, dass die Wiederholung modulo <math>p</math> erheblich früher als die Wiederholung modulo <math>n</math> einsetzt.

Bei einer derart berechneten Zahlenfolge mit endlich vielen möglichen Funktionswerten werden zunächst in einer Vorperiode einige Werte
:<math>x_0,  x_1, \ldots, x_{k - 1}</math>

angenommen. Sobald ein Wert wiederholt auftritt, wiederholen sich die Werte anschließend zyklisch
:<math>x_k, x_{k+1}, \ldots,  \left( x_{k+l} = x_k \right), x_{k+1}, \ldots</math>

Dieses Verhalten der Folge gab der Methode ihren Namen, da man sich die Periode wie einen Kreis vorstellen kann und die Folgenglieder am Anfang wie einen Stängel, der in den Kreis hineinführt. Graphisch sieht das aus wie der griechische Buchstabe [[Rho|ρ]].

Haben zwei Werte <math>x</math> und <math>y</math> modulo <math>p</math> aus der Folge den gleichen Wert, für die folglich <math>x\equiv y \pmod p\ </math> gilt, so ergibt der [[Größter gemeinsamer Teiler|größte gemeinsame Teiler]] <math>\operatorname{ggT}(x-y , n)</math> ein Vielfaches von <math>p</math> und oftmals einen echten Teiler von <math>n</math>.

Es ist jedoch sehr aufwändig, alle Zahlenwerte auf diese Weise zu vergleichen. Eine optimierte Variante der Pollard-Rho-Methode berechnet daher zur Bestimmung der Periodenlänge zwei Folgen. Eine Folge
:<math> x = (x_1, x_2, x_3, x_4, \ldots)</math>

und die zweite Folge
:<math> y = (y_1, y_2, y_3, y_4, \ldots) = (x_2, x_4, x_6, x_8, \ldots)</math>

Durch diesen Trick kann der Vergleich sehr vieler Funktionswerte vermieden werden. Es muss jetzt nicht für alle Paare <math>(x_i, x_j)</math> der größte gemeinsame Teiler <math>\operatorname{ggT}(x_i - x_j, n)</math> berechnet werden. Es genügt jeweils, <math>\operatorname{ggT}(x_i - y_i, n)</math> bzw. <math>\operatorname{ggT}(x_i - x_{2i}, n)</math> zu berechnen.

Da <math>p</math>, als ein gesuchter Teiler von <math>n</math>, unbekannt ist, kann zunächst der Rest der Division durch <math>p</math> nicht berechnet werden. Es wird daher nicht die Gleichheit zweier Werte <math>x</math> und <math>y</math> abgefragt, sondern der <math>\operatorname{ggT}(x-y,n)</math> berechnet. Falls sich die Werte <math>x</math> und <math>y</math> nur um ein Vielfaches von <math>p</math> unterscheiden, ist der Wert des <math>\operatorname{ggT}(x-y, n)</math> ein Vielfaches des gesuchten Teilers <math>p</math> von <math>n</math>. Ganzzahlige Vielfache von <math>n</math> sind zugleich ganzzahlige Vielfache von <math>p</math> und brauchen deshalb bei der Berechnung nicht berücksichtigt werden. Infolgedessen genügt es die Funktionswerte modulo <math>n</math> zu berechnen.

Zur Berechnung der Zahlenfolge kann eine Funktion der Form <math>f(x)=x^2+ const</math> benutzt werden. Durch diese Wahl können nur ein Teil, etwa die Hälfte, der Werte <math>0</math> bis <math>p-1</math> bei der Restbildung auftreten, wodurch das frühzeitigere Auftreten der gesuchten Wiederholungen etwas begünstigt wird.

=== Formale Definition ===

Sei <math>n</math> die Zahl, von der ein Primfaktor <math>p</math> berechnet werden soll. Bezeichne <math>(x_k)_{k \in \mathbb{N}}</math> eine Folge von Pseudozufallszahlen wie zum Beispiel
:<math>\begin{align}
x_0 &= 2\\
x_{k+1} &= x_k^2 + c \pmod n \quad\text{ mit }\quad c \not\equiv 0\pmod n \text{ und }c \not\equiv -2\pmod n.
\end{align}</math>

Existiert ein echter Primfaktor <math>p</math>, so gilt
:Es gibt einen Index <math>i < p</math>, so dass <math>n > k_i > 1</math> und <math>k_i \,|\, n</math> mit <math>k_i = \operatorname{ggT}(|x_i - x_{2i}|,n)</math>.

== Algorithmus ==

''Eingabe'': <math>n</math> ist die zu faktorisierende Zahl und <math>f(x)</math> sei die Pseudo-Zufallsfunktion modulo <math>n</math><br />
''Ausgabe'': Ein nicht-trivialer Faktor von <math>n</math> oder eine Fehlermeldung
# ''x'' ← 2, ''y'' ← x; ''d'' ← 1
# Solange ''d'' = 1:
##''x'' ← ''f''(''x'')
## ''y'' ← ''f''(''f''(''y''))
## ''d'' ← ggT(|''x'' − ''y''|, ''n'')
# Wenn 1 &lt; ''d'' &lt; ''n'', dann ''d zurückgeben''.
# Falls ''d'' = ''n'', dann „Fehler“ ausgeben.

Anmerkung: Dieser Algorithmus liefert für alle <math>n</math>, die nur durch 1 und sich selbst teilbar sind, eine Fehlermeldung zurück. Allerdings kann auch für die anderen <math>n</math> eine Fehlermeldung zurückgeliefert werden. In diesem Fall wählt man eine andere Funktion <math>f(x)</math> und versucht es erneut.

Ist das Ergebnis eine Zahl, so ist diese wirklich auch ein Teiler und damit ein korrektes Ergebnis, wobei dieses im Allgemeinen nicht zwingend eine Primzahl sein muss.

Für <math>f</math> wählt man ein Polynom mit einem ganzzahligen Koeffizienten. Eine übliche Funktion <math>f(x)</math> für diesen Algorithmus hat folgende Form:

:<math>f(x)=x^2+c\hbox{ mod }n,\,c\neq0,-2.</math>

== Abschätzung der Laufzeit ==

Die Zahlenfolgen <math>x_i \bmod p</math> und <math>x_{2i} \bmod p</math> können als Pseudo-Zufallsfolgen angesehen werden. Falls ein Zahlenwert erneut auftritt, wiederholen sich zwangsläufig die folgenden Werte. Es können bis zu <math>p</math> Werte angenommen werden (bei quadratischem <math>f</math> wie oben: bis zu <math>\tfrac{p+1}2</math> Werte). Der [[Erwartungswert]] für die Länge eines Zyklus beträgt <math>\sqrt{p}</math>. Die Tatsache, dass weit weniger als <math>p</math> Berechnungen erforderlich sind, wird zuweilen [[Geburtstagsparadoxon]] genannt.

Der ungünstigste Fall tritt ein, wenn <math>n</math> ein Produkt von zwei Primzahlen gleicher Länge ist. Der Algorithmus terminiert dann nach [[Landau-Symbole|O]](n<sup>1/4</sup> ''[[Polylogarithmus|polylog]]''(n)) Schritten mit einer Wahrscheinlichkeit von <math>\tfrac12</math>. Die Methode ist gut geeignet, um Zahlen mit mehreren kleineren Faktoren zu faktorisieren. Der Algorithmus kann in der gleichen Zeit (mit hoher Wahrscheinlichkeit) eine Zahl mit doppelt so vielen Stellen wie die [[Probedivision]] faktorisieren. Der Algorithmus arbeitet [[exponentiell]] in der Länge der Eingabe und ist damit asymptotisch langsamer als das [[Quadratisches Sieb|Quadratische Sieb]] und das [[Zahlkörpersieb]].

== Zahlenbeispiel ==
[[Datei:Pollard Rho.png|rechts|Feder]]
'''1. Beispiel'''

Gesucht seien die Faktoren der Zahl <math>n=703</math>. Wir verwenden die Funktion <math>f(x)=x^2+23 \mod n</math> und den Startwert <math>x_0=431</math>:

{| class="wikitable" style="text-align:center"
|+ Tabelle: Rho-Methode für ''n'' = 703
|-
|colspan="4"| <math>n=703, \quad f(x)=x^2+c</math> mit <math>c=23, \quad x_0=431</math>
|- class="hintergrundfarbe5"
| <math>i</math> || <math>x_i=f(x_{i-1})</math> || <math>y_i = x_{2 \cdot i} = f(f(y_{i-1}))</math> || <math>d={\operatorname{ggT}(|x-y|,n})</math>
|-
|1 ||192 ||331 ||1
|-
|2 ||331 || 49 ||1
|-
|3 ||619 ||125 ||'''19'''
|-
|4 || 49 ||106 ||19
|-
|5 ||315 ||144 ||19
|-
|6 ||125 ||619 ||19
|-
|7 ||182 ||315 ||19
|-
|8 ||106 ||182 ||19
|-
|9 || 11 || 11 ||703
|-
|10 ||144 ||372 ||19
|-
|11 ||372 ||49 ||19
|-
|12 || 619 ||125 ||19
|}

Damit ist die Primfaktorzerlegung von <math>703=19\cdot 37</math> gefunden.

'''2. Beispiel'''

{| class="wikitable" style="text-align:center"
|+ Tabelle: Rho-Methode für ''n'' = 2717
|-
|colspan="4"|<math>n=2717, \quad f(x)=x^2+c</math> mit <math>c=4, \quad x_0=2</math>
|- class="hintergrundfarbe5"
| <math>i</math> || <math>x_i=f(x_{i-1})</math> || <math>y_i = x_{2 \cdot i} = f(f(y_{i-1}))</math> || <math>d={\operatorname{ggT}(|x-y|,n})</math>
|-
|1 ||   8 ||  68 || 1
|-
|2 ||  68 || 277 ||'''209'''
|-
|3 ||1911 ||2367 ||19
|-
|4 ||277  ||68   ||209
|-
|5 ||657  ||277  ||19
|-
||6 || 2367 || 2367 || 2717
|-
||7 || 239 || 68 || 19
|-
|8 ||68 || 277 || 209
|}
Dieses Beispiel zeigt, dass der gefundene Faktor nicht zwingend eine Primzahl sein muss. Der hier gefundene Faktor ist <math>209=11\cdot 19</math>.

== Faktorisierungen ==
Mit der beschriebenen Methode konnte 1980 die [[Fermat-Zahl]]
:<math>F_8 = 2^{2^{8}}+1= 2^{256} + 1 = 1238926361552897 \cdot p_{62}</math>
faktorisiert werden. <math>p_{62}</math> bezeichnet dabei eine (Prim)Zahl mit 62 Stellen, von der erst später bewiesen wurde, dass es sich bei ihr um eine Primzahl handelt.

== Implementierungen ==
Die Rho-Methode ist unter dem Namen <code>rho_factorize()</code> Bestandteil der Funktionsbibliothek des Programms [[ARIBAS]] von [[Otto Forster]].

== Literatur ==
* ''A Monte Carlo Method for Factorization'', J.M.Pollard, BIT 15 (1975) 331–334
* ''An Improved Monte Carlo Factorization Algorithm'', R.P.Brent, BIT 20 (1980) 176–184
* Otto Forster: ''Algorithmische Zahlentheorie.'' Vieweg, 1996, ISBN 3-528-06580-X

== Weblinks ==
* [https://mathworld.wolfram.com/PollardRhoFactorizationMethod.html Pollard Rho Methode in der Mathworld]
* [http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/Factor/RhoFac.html Applet für Pollard-Rho Faktorisierung]

[[Kategorie:Zahlentheoretischer Algorithmus]]
[[Kategorie:Faktorisierungsverfahren]]