2.4.1 Rho-Faktorisierung von Pollard

Pollards Rho-Faktorisierung ist ein spezieller Algorithmus um kleine Primfaktoren zu finden. Betrachte man dabei folgenden Satz:

Sei f: S→S eine beliebige Funktion, wobei S eine endliche Menge sei mit |S| = n. Sei weiter x₀ ∈ S, beliebig. Betrachten wir nun die Folge x₀, x₁, x₂, ... welche durch x_i+1 = f(x_i ) definiert sei. Da S endlich ist, muss die Folge in einem Zyklus enden und einen Rumpf besitzen.

Möchte man nun die Länge des Zyklus herausfinden, so eignet sich folgender Algorithmus dafür (Floyd's Zyklen-Such-Algorithmus):

Bei dieser Methode beginnt man mit einem Paar (x₁ , x₂ ) und berechnet iterativ (x_i , x_2i ) aus dem vorherigen Paar (x_i-1 , x_2i-2 ) bis man ein Duplikat x_m = x_2m erhält. ⇒ Falls der Rumpf eine Länge von λ hat und der Zyklus eine Länge von μ, so ist das erste Mal, wenn x_m = x_2m ist, m = μ (1 + ⌊λ / μ ⌋ ).

Pollard's Rho-Algorithmus verwendet nun Floyd's Algorithmus um in der Folge der Ganzzahlen y₀, y₁, y₂, ..., y_i ∈ Z ∀ i, ein solches Duplikat zu finden. Die Folge wird dabei folgendermaßen definiert: y₀ = 2, y_i+1 = f(y_i ) = (y_i² + 1) mod p, i ≥ 0. Floyd's Algorithmus wird nun verwendet, um y_m und y_2m zu finden mit y_m ≡ y_2m (mod p). Da p n teilt, jedoch nicht bekannt ist, wird dies durch die Ausdrücke y_i mod n berechnet, und getestet, ob der ggT(y_m - y_2m , n ) > n ist. Falls nun also ein solches m gefunden ist und ggT(y_m - y_2m , n ) < n, dann hat man einen nicht-trivialen Faktor von n erhalten ( = n tritt mit geringer Wahrscheinlichkeit auf).

Beispiel:

Sei n = 221. Man beginnt mit:

y₀ = 2
y₁ = f(y₀ ) = ((y₀ )² + 1) mod n = 5, y₂ = f( f( y₀ )) = 26, d = ggT(y₁ - y₂ , n ) = ggT ( 21, 221 ) = 1,
y₂ = 26, y₄ = 197, d = ggT ( 26 - 197, 221 ) = 1,
y₃ = 26² + 1 mod 221 = 14, y₆ = 104, d = ggT ( 90, 221 ) = 1,
y₄ = 197, y₈ = 145, d = 13,
Damit ist 13 ein nicht-trivialer Primfaktor von 221 und der andere nicht-triviale Faktor ist 221 / 13 = 17.

Falls der Algorithmus scheitert, so kann man es mit einer anderen Funktion f mit anderem Ganzzahlkoeffizienten etwa f = x² + c , c ≠ 0, -2 versuchen.
Man bedenke jedoch, dass dieser Algorithmus in erster Linie für zusammengesetzte Ganzzahlen, die nicht Potenzen von Primzahlen sind, gedacht ist.

Applet Rho-Faktorisierung:

Quellcode:
RhoFacSF.java - Appletoberfläche
RhoFac.java - Algorithmenklasse

2.4.2 (p-1)-Faktorisierung