Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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ückfü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 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) erkennen lässt. Daraus leitet sich die Bezeichung der Methoden ab.

Inhaltsverzeichnis 1 Funktionsweise 1.1 Formale Definition 2 Algorithmus 3 Abschätzung der Laufzeit 4 Zahlenbeispiel 5 Verbesserte Verfahren zur Faktorisierung 6 Literatur 7 Weblinks

Funktionsweise

Gesucht ist ein Primfaktor p der Zahl n. 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 f: N -> N verwendet werden.

Die Folge startet mit einem weitgehend beliebig wählbaren Startwert x₀. 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, ... , p - 1 annehmen. Tritt einer dieser Werte erneut auf, so wiederholen sich anschließend diese Werte modulo p. Dies geschieht spätestens nach p Iterationen und im Mittel nach etwa Iterationen.

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

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

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 y mod p gilt, so ergibt ggT(x - y, n) ein Vielfaches von p und oftmals einen echten Teiler von n.

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

und die zweite Folge

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 n, 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. Ganzzahlige Vielfache von n sind zugleich ganzzahlige Vielfache von p und brauchen deshalb bei der Berechnung nicht berücksichtigt werden. Infolgedessen genügt es die Funktionswerte modulo n zu berechnen.

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.

Formale Definition

Sei n die Zahl, von der ein Primfaktor ρ berechnet werden soll.

Faktor ρ ← { ∀n : ∃ i < ρ : ggT(|x_i - x_2i|, n) > 1 mit x_i ← (x_i-1)² + c für c ∈ N, wobei x₀=2 und c ≠ -2, 0 }

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 eine Fehlermeldung

1. x ← 2, y ← x; 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 then 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 Fehlermeldung zurückgeliefert 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 Teiler und damit ein korrektes Ergebnis, wobei dieses im Allgemeinen nicht zwingend eine Primzahl sein muss.

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

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 . Die Tatsache, dass weit weniger als p Berechnungen erforderlich sind, wird zuweilen Geburtstagsparadoxon genannt. Da die Folge jedoch weniger als p Werte modulo p annehmen kann und n mindestens einen Faktor kleiner als 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

1. Beispiel

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

x₁=(431²+23)mod 703=192,  y₁=x₂=(((431²+23)mod 703)²+23)mod 703=331,  ggT(192-331,703)=1

x₂=(192²+23)mod 703=331,  y₂=x₄=(((331²+23)mod 703)²+23)+23)mod 703=49,  ggT(331-49,703)=1

x₃=(331²+23)mod 703=619,  y₃=x₆=(((49²+23)mod 703)²+23)+23)mod 703=125,  ggT(619-125,703)=19

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

x₄=(619²+23)mod 703=49

x₅=(49²+23)mod 703=315

x₆=(315²+23)mod 703=125  <= Hier wird der Primfaktor ermittelt.

x₇=(125²+23)mod 703=182

x₈=(182²+23)mod 703=106

x₉=(106²+23)mod 703=11

x₁₀=(11²+23)mod 703=144

x₁₁=(144²+23)mod 703=372

x₁₂=(372²+23)mod 703=619 =x₃

x₁₃=(619²+23)mod 703=49 =x₄

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

Das ganze in tabellarischer Form:

n = 703,   f(x) = x2 + c mit c = 23,   x0 = 431
i	xi = f(xi-1)	yi = x2i = f(f(yi-1))	d = ggT(|x-y|, n)
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

2. Beispiel

Weiteres Beispiel in tabellarischer Form:

n = 2717,   f(x) = x2 + c mit c = 4,   x0 = 2
i	xi = f(xi-1)	yi = x2i = f(f(yi-1))	d = ggT(|x-y|, n)
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 209 = 11 * 19.

3. Beispiel

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

x₁=(1²+12)mod 16061993=13,  x₂=(((1²+12)mod 16061993)²+12)mod 16061993=181,  ggT(13-181,16061993)=1

x₂=(13²+12)mod 16061993=181,  x₄=(((181²+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 faktorisiert werden. Diese Zahl hat 257 Bit. 2005 wurde mit einem optimierten Verfahren die Zahl RSA-200 mit 663 Bit faktorisiert und bereits 1988 gelang es Brent und Morain, F₁₁ mit 2049 Bit vollständig zu faktorisieren.

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

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Pollard-Rho-Methode, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.