Pollard-Rho-Methode

Die Pollard-Rho-Methoden sind Algorithmen zur Bestimmung der Periodenlänge einer Zahlenfolge, die mit einer mathematischen Funktion berechnet wird. Verschiedene schwierige mathematische Probleme wie der diskrete Logarithmus und die Primfaktorzerlegung lassen sich auf die Bestimmung der Periodenlänge zurüchführen. 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 Kollisionen in Hashfunktionen anwenden.

Funktionsweise

Gesucht ist ein Teiler p, nicht zwingend eine Primzahl, der Zahl n. Das Verfahren beruht auf der Erzeugung einer zufälligen Zahlenfolge aus Pseudozufallszahlen. Zur Erstellung der Zufallsfolge kann eine relativ beliebige Funktion verwendet werden.

Die Folge startet mit einem weitgehend beliegig wählbarem Startwert $x_{0}$. Die weiteren Werte werden iterativ berechnet gemäß $x_{i}=f(x_{i-1})$. Die Funktionswerte modulo p können maximal die p verschiedenen Werte 0,1,2, ..., und p-1 annehmen. Tritt einer dieser Werte erneut auf, wiederholen sich anschließen diese Werte moduo p. Dies geschieht spätestens nach p-Iterationen und im Mittel nach etwa ${\sqrt {p}}$ Iterationen. Wir können diese Reste zunächst nicht berechnen, da p als gesuchter Wert unbekannt ist. Dies spielt jedoch keine Rolle. Wir betrachen gedanklich die Reste der Division durch p.

Bei einer derart berechneten Zahlenfolge mit endlich vielen möglichen Funktionswerten werden zunächst in einer Vorperiode einige Werte

$f_{0},\,f_{1},\,...,f_{k-1}$

angenommen. Sobald ein Wert wiederholt auftritt, wiederholen sich die Werte anschließlich zyklisch

$f_{k},\,f_{k+1}\,,...,f_{k+l}=f_{k},f_{k+1},\cdots$

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 Stengel, der in den Kreis hineinführt. Graphisch sieht das aus wie der griechische Buchstabe ρ.

Haben zwei Werte x und y modulo p aus der Folge den gleichen Wert, für die folglich x $\equiv$ y modulo p gilt, so ergibt ggT(x-y,n) ein Vielfaches von p und oftmals einen echten Teiler von n.

Es ist jedoch sehr aufwendige alle Zahlenwerte auf diese Weise zu vergleichen. Eine optimierte Varianate der Pollard Rho Methode berechnet daher zur Bestimmung der Periodenlänge zwei Folgen. Eine Folge

$x=(x_{0},\,x_{1},\,x_{2},\,a_{3},\,a_{4},\,...)$

und die zweite Folge

$y=(y_{0},\,y_{1},\,y_{2},\,y_{3},\,y_{4},\,...)=(x_{0},\,x_{2},\,x_{4},\,x_{6},\,x_{8},\,...).$

Durch diesen Trick kann der Vergleich sehr vieler Funktionswerte vermieden werden. Es muss jetzt nicht für alle Paare $(x_{i},x_{j})$ der größte gemeinsame Teiler ggT$(x_{i}-x_{j},n)$ berechnet werden. Es genügt jeweils den ggT$(x_{i}-y_{i},n)$ bzw. ggT$(x_{i}-x_{2i},n)$ zu berechnen.

Da p als ein gesuchter Teiler von unbekannt ist, kann zunächst der Rest der Division durch p nicht berechnet werden. Es wird daher nicht die Gleichheit zweier Werte x und y abgefragt, sondern der ggT(x - y, n) berechnet. Falls sich die Werte x und y nur um ein Vielfaches von p unterscheiden, ist der Wert des ggT(x-y,n) ein Vielfaches des gesuchten Teilers p von n. Ganzahlige Vielfache von n sind zugleich ganzzahlige Vielfache von p, die bei der Berechnung nicht berüchsichtigt werden brauchen. Die Funktionswerte können daher zur Vereinfachung modulo n berechnet werden.

Zur Berechnung der Zahlenfolge kann eine Funktion der Form f(x)=x² + const benutzt werden. Durch diese Wahl können nur ein Teil, etwa die Hälfte, der Werte 0 bis p-1 bei der Restbildung auftreten.

Algorithmus

Eingabe: n ist die zu faktorisierende Zahl und f(x) sei die Pseudo-Zufallsfunktion modulo n
Ausgabe: Ein nicht-trivialer faktor von n, oder Fehlmeldung

1. x ← 2, y ← 2; d ← 1
2. While d = 1:
   1. x ← f(x)
   2. y ← f(f(y))
   3. d ← ggT(|x − y|, n)
   4. If 1 < d < n, then return d.
   5. If d = n, return "Fehler".

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

Ist das Ergebnis eine Zahl, so ist diese wirklich auch ein Primfaktor und damit ein korrektes Ergebnis. Kurzum, der Pollard-Rho-Algorithmus liefert nie ein inkorrektes Ergebnis.

Für f wählt man ein Polynom mit einem ganzzahligem Koeffizienten. Eine übliche Funktion für diesen Algorithmus hat folgende Form:

$f(x)=x^{2}+c{\hbox{ mod }}n,\,c\neq 0,-2.$

Alternative Schreibweise des Algorithmuses

1. x₀ ← 2; d ← 1
2. While d = 1:
   1. x_i ← f(x_i-1)   (falls noch nicht berechnet)
   2. x_2i ← f(x_2i-1)
   3. d ← ggT(|x_i − x_2i|, n)
   4. If 1 < d < n, then return d.
   5. If d = n, return "Fehler"

Abschätzung der Laufzeit

Die Zahlenfolgen $x_{i}$ mod p und $x_{2i}$ mod p können als Pseudo-Zufallsfolgen angesehen werden. Falls ein Zahlenwert erneut auftritt, wiederholen sich zwangsläufig die folgenden Werte. Es können bis zu p-Werte angenommen werden. Der Erwartungswert für die Länge eines Zyklus beträgt im Durchschnitt ${\sqrt {p}}$. Die Tatsache, dass weit weniger als p Berechnungen erforderlich sind, wird zuweilen Geburtstagsparadoxon genannt. Da sich die Folge jedoch weniger als p Werte modulo p annehmen kann und n mindestens einen Faktor kleiner als ${\sqrt {n}}$ besitzt, ist das Verfahren auch im ungünstigsten Fall nicht wesentlich langsamer als die Probedivision.

Diese Überlegung gilt natürlich für alle Primfaktoren, so dass die Methode gut geeignet ist, Zahlen mit mehreren kleineren Faktoren zu faktorisieren.

Zahlenbeispiel

Feder

• Gesucht seien die Faktoren der Zahl n=703. Wir verwenden die Funktion f(x)=x²+23 und den Startwert x₀=431.

x₁=($431^{2}$+23)mod 703=192,  x₂=((($431^{2}$+23)mod 703)²+23)mod 703=331,  ggT(192-331,703)=1

x₂=($192^{2}$+23)mod 703=331,  x₄=((($331^{2}$+23)mod 703)²+23)+23)mod 703=49,  ggT(331-49,703)=1

x₃=($331^{2}$+23)mod 703=619,  x₆=((($49^{2}$+23)mod 703)²+23)+23)mod 703=125,  ggT(619-125,703)=19

Damit ist die Primfaktorzerlegung von 703=19·37 gefunden.

x₄=($619^{2}$+23)mod 703=49

x₅=($49^{2}$+23)mod 703=315

x₆=($315^{2}$+23)mod 703=125  <= Hier wird der Primfaktor ermittelt.

x₇=($125^{2}$+23)mod 703=182

x₈=($182^{2}$+23)mod 703=106

x₉=($106^{2}$+23)mod 703=11

x₁₁=($11^{2}$+23)mod 703=144

x₁₂=($144^{2}$+23)mod 703=372

x₁₃=($372^{2}$+23)mod 703=619 =x₃

x₁₄=($619^{2}$+23)mod 703=49 =x₄

Das periodische Verhalten ist nun erkennbar. Es entsteht ein Zyklus ab x₁₃.

• Gesucht seien die Faktoren der Zahl 16061993. Mit f(x)=x²+12 und dem Startwert x₀=1 erhält nach 18 Schritten den Faktor 4657:

x₁=($1^{2}$+12)mod 16061993=13,  x₂=((($1^{2}$+12)mod 16061993)²+12)mod 16061993=181,  ggT(13-181,16061993)=1

x₂=($13^{2}$+12)mod 16061993=181,  x₄=((($181^{2}$+12)mod 16061993)²+12)mod 16061993=13978003,  ggT(181-13978003,16061993)=1

x₃=32773,  x₆=8711797,  ggT(32773-8711797,16061993)=1

x₄=13978003,  x₈=7982227,  ggT(13978003-7982227,16061993)=1

x₅=12032842,  x₁₀=4985718,  ggT(12032842-4985718,16061993)=1

x₆=8711797,  x₁₂=8138577,  ggT(8711797-8138577,16061993)=1

x₇=435306,  x₁₄=2566882,  ggT(435306-2566882,16061993)=1

x₈=7982227,  x₁₆=10372210,  ggT(7982227-10372210,16061993)=1

x₉=13335673,  x₁₈=5638320,  ggT(13335673-5638320,16061993)=1

x₁₀=4985718,  x₂₀=12304164,  ggT(4985718-12304164,16061993)=1

x₁₁=4228666,  x₂₂=5872876,  ggT(4228666-5872876,16061993)=1

x₁₂=8138577,  x₂₄=11257858,  ggT(8138577-11257858,16061993)=1

x₁₃=4913534,  x₂₆=15071483,  ggT(4913534-15071483,16061993)=1

x₁₄=2566882,  x₂₈=7315289,  ggT(2566882-7315289,16061993)=1

x₁₅=12743441,  x₃₀=9148207,  ggT(12743441-9148207,16061993)=1

x₁₆=10372210,  x₃₂=15066270,  ggT(10372210-15066270,16061993)=1

x₁₇=9091895,  x₃₄=11187185,  ggT(9091895-11187185,16061993)=1

x₁₈=5638320,  x₃₆=13536592,  ggT(5638320-13536592,16061993)=4657

Zum Vergleich: Mit Probedivision hätte man, selbst wenn man bei der Probedivision nur Primzahlen benutzt, 630 Schritte gebraucht.

Verbesserte Verfahren zur Faktorisierung

Mit der beschriebenen Methode konnte 1980 die Fermat-Zahl $F_{8}=2^{2^{8}}+1=2^{256}+1$ faktorisiert werden. Diese Zahl hat 256 Bit. 2005 wurde mit einem optimierten Verfahren die Zahl RSA-200 mit 663 Bit faktorisiert und bereits 1988 gelang es Brent und Morain $F_{11}$ mit 2048 Bit vollständig zu faktoriesieren.

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

Weblinks

• Pollard Rho Methode in der Mathworld
• Applet für Pollard-Rho Faktorisierung