Pollard-p-1-Methode

Die Pollard-p-1-Methode ist ein Verfahren zur Faktorisierung von zusammengesetzten Zahlen. Sie wurde 1974 von John M. Pollard beschrieben.

Mathematische Grundlagen

Die p-1 Faktorisierungsmethode von Pollard basiert auf dem kleinen fermatschen Satz. Sei p eine Primzahl, und a eine Zahl, die nicht von p geteilt wird, dann gilt

$a^{p-1} \equiv 1 \pmod{p}$.

Ebenso gilt dann $a^m \equiv 1 \pmod{p}$ für alle Vielfachen m von p-1. Das bedeutet, dass a^m-1 ein Vielfaches von p ist. Wenn nun N eine zu faktorisierende Zahl mit (unbekanntem) Primteiler p ist, teilt dieses p den ggT(a^m − 1,N), da es beide Zahlen teilt, von denen der ggT gebildet wurde. Meist ist dieser ggT ein echter Teiler von N. Im folgenden Absatz wird eine Methode beschrieben, wie man eine passende Zahl m finden kann.

Die 1. Phase des Verfahrens

Sei nun eine zu faktorisierende natürliche Zahl N gegeben. Insbesondere sei N eine zusammengesetzte Zahl. Man wählt eine Zahl a, die teilerfremd zu N ist. Anhand einer Heuristik bestimmt man eine weitere Zahl B, von der man annimmt, dass für jeden Primteiler p von N die Zahl p-1 B-potenzglatt ist. Das heißt, für jeden Primteiler q von p-1 gilt:

$q^{e_q\left(p-1\right)} \leq B$

Die Zahl e_q(p-1) bezeichnet den q-Exponenten von p-1. Er gibt an, wie oft die Zahl q in der Primfaktorzerlegung von p-1 auftritt. Ersetzt man in der Ungleichung die Zahl p-1 durch eine beliebige B-potenzglatte Zahl m, so bleibt die Ungleichung wahr. Umformen nach dem q-Exponenten liefert:

$e_q\left( m \right) \leq \frac{\log B}{\log q}$

Sind B und q fix gewählt, so gibt diese Formel eine scharfe obere Grenze für den q-Exponenten an. Ist dieser größer als die rechte Seite der Ungleichung, so ist m nicht mehr B-potenzglatt. Man setzt nun

$f_q = \left\lfloor \frac{\log B}{\log q} \right\rfloor$

Das ist der größte q-Exponent, den eine B-potenzglatte Zahl m haben kann. Man erstellt als nächstes eine Liste F, in welcher die Primzahl q genau f_q-mal vorkommt. Die Primzahlen in der Liste werden mit q₁, q₂, q₃, ... , q_R durchnummeriert, wobei R die Anzahl der Listenelemente von F ist. Das Produkt aller Zahlen in F wird mit M bezeichnet. Nach Konstruktion ist M B-potenzglatt. Es ist sogar die größte B-potenzglatte Zahl.

Besitzt N zumindest einen Primteiler p mit p-1 B-potenzglatt, so ist M ein Vielfaches dieser Zahl p-1. Es ist daher (siehe voriger Absatz) ggT(N,a^M − 1) ein echter Teiler von N, oder gleich N. In der Regel reicht eine kleinere Potenz von a als die M-te aus, um einen Teiler zu erhalten. Die praktische Vorgehensweise ist daher die folgende: Man berechnet iterativ

a₀ = a

$a_{i+1}=a_i^{q_i}$ für i = 1,...,R

Dabei werden in jedem Schritt die auftretenden Potenzen durch ihre Reste modulo N ersetzt. Nach einer bestimmten Anzahl von Schritten, z. B. dem 20., überprüft man, ob man bereits einen Teiler gefunden hat. Das heißt, man betrachtet ggT(a₂₀ − 1,N). Ist dieser ggT größer als 1, so hat man einen Teiler bestimmt, und bricht das Verfahren ab; ist der ggT gleich 1, so fährt man in 20er-Schritten fort, bis man einen Teiler gefunden oder a_R = a^M erreicht hat.

Insgesamt können am Ende drei Fälle auftreten:

1. Man findet einen echten Teiler von N. In diesem Fall war das Verfahren erfolgreich, und man hat N in zwei Faktoren zerlegt. Gegebenenfalls kann man das Verfahren erneut auf diese beiden Zahlen anwenden, bis man die Primfaktorzerlegung von N erhält, oder für einen der Faktoren von N Fall 3 auftritt.
2. Man findet den Teiler N von N. Dieser Fall ist nicht besonders wahrscheinlich, kann aber auftreten. In diesem Fall ist es ratsam, einen anderen Wert für a zu wählen.
3. Man findet den Teiler 1 von N. In diesem Fall war die Annahme, dass es einen Teiler p von N gibt, für den p-1 B-potenzglatt ist, falsch. In diesem Fall sollte man die 2. Phase der p-1-Methode starten.

Die 2. Phase des Verfahrens

Versagt das Verfahren in der 1. Phase, so liegt die Ursache oft darin, dass die für die Primfaktoren p von N gilt, dass $p-1=u\cdot l$. Dabei ist u B-glatt oder sogar B-potenzglatt, und l eine Primzahl, die größer als B ist. Mit anderen Worten: p-1 ist nur wegen eines einzigen Primfaktors nicht B-(potenz-)glatt.

Man wählt daher eine zweite Schranke B₁, um den Faktor l „einzufangen“. B₁ sollte wesentlich größer als B gewählt werden, aber nicht größer als B². Häufig wählt man B₁ im Bereich von B^4/3.

Analog zur ersten Phase erstellt man die Liste F₁ der Primzahlen die zwischen B und B₁ liegen. Dabei speichert man die erste dieser Zahlen als l₁, und trägt in die Liste die Differenzen zwischen benachbarten Primzahlen ein. Die Anzahl der Elemente von F₁ sei S. Beachte: Für B₁ < 20.000.000 ist jede dieser Differenzen kleiner oder gleich 200. Es treten also nur wenige, und nur kleine Differenzen auf.

Als Startwert für die 2. Phase dient die Zahl a_R, welche am Ende der 1. Phase berechnet wurde. Als weitere Vorbereitung berechnet man für jede Differenz d in F₁ die Zahl

$j_d = a_R^d$ (genauer: den Rest dieser Zahl modulo N)

Einerseits müssen hier nur wenige j_d berechnet werden, andererseits wird nur eine kleine Potenz benötigt. Wie in Phase 1 startet man nun wieder eine Iteration. Dabei kann man das aufwändige Potenzieren durch Multiplikationen ersetzen.

$a_{R+1} = a_R^{l_1}$

$a_{R+i} = a_{R+i-1} \cdot {j_d}_i = a_R^{l_{i-1}} \cdot a_R^{d_i} = a_R^{l_{i-1}+d_i} = a_R^{l_i}$ für i = 2,3,...,S

Dabei sei d_i die Differenz zwischen der (i-1)-ten und der i-ten Primzahl in F₁. Wiederum ersetzt man die Zahlen in jedem Schritt durch ihre Reste modulo N.

Anders als in Phase 1 reicht es nicht aus, nach einer festen Anzahl von Schritten den ggT(a_{R + i} − 1,N) zu bilden. Stattdessen muss man die Zahlen a_R+i-1 akkumulieren, d. h. man bildet das Produkt all dieser Zahlen. Das kann im Zuge der obigen Iteration mit erledigt werden, indem man z₁=a_R+1-1, und z_i=z_i-1*(a_R+i-1) setzt. Durch das Akkumulieren erreicht man, dass auch Primfaktoren p von N gefunden werden können, bei denen mehr als ein Primfaktor von p-1 größer als B ist.

Nach einer festen Anzahl von Schritten, etwa wieder jedem 20., bildet man ggT(z_i,N). Wieder können am Ende die drei Fälle auftreten, die am Ende von Phase 1 auftreten konnten. Versagt das Verfahren, so kann man die Schranken B und B₁ vergrößern, und das Verfahren erneut starten. Besser ist es allerdings, in diesem Fall ein anderes Verfahren zu verwenden.

Die Heuristik des größten Primteilers

Eine natürliche Zahl m hat im Durchschnitt log log m Primteiler. Diese Aussage lässt sich präzise formulieren und beweisen. Man tut so als hätte die Anzahl der Primteiler von m genau diesen Wert, d. h. man nimmt an, dass

$\omega \left( m \right) = \log \log m$

Es sei nun q der größte Primteiler von m. Dann gilt:

$\omega \left( \frac{m}{q} \right) = \omega(m)-1$

Auflösen dieser Gleichung nach q liefert:

$q=m^{1-\frac{1}{e}}$

Dabei ist e die Eulersche Zahl. Das ist eine heuristische Begründung dafür, dass der größte Primteiler von m etwa gleich m^0.632 ist. Dieser Sachverhalt wird genutzt, um einen Wert für die Suchschranke B aus dem obigen Verfahren zu bestimmen.

Anwendung auf das Verfahren

Sei nun N eine zusammengesetzte natürliche Zahl, auf die man die p-1-Methode anwenden möchte. Da sie zusammengesetzt ist, besitzt sie einen Primteiler p ≤ $\sqrt{N}$. Nach der Heuristik gilt für den größten Primteiler q von p-1

$q \le \left( p-1 \right)^{1-\frac{1}{e}} \le n^{\frac{1}{2}(1-\frac{1}{e})} \approx n^{0.316}$

Wählt man also B ≥ N^0,316, so ist zu erwarten, dass p-1 B-glatt ist. Die B-Potenzglattheit lässt sich nun so erreichen: Angenommen p-1 sei B-glatt. Dann gilt für alle Primteiler q von p-1:

$q^{e_q(p-1)} \le n^{\frac{1}{2}} \le B^{\frac{e}{e-1}}$

Wie in der Beschreibung der 1. Phase (siehe oben) erhält man daraus für eine B-potenzglatte Zahl m:

$e_q(m) \le \left\lfloor \frac{e}{e-1} \frac{\log B}{\log q} \right\rfloor \approx 1,6 \cdot f_q$

Die Zahl f_q ist hier dieselbe, die in der 1. Phase berechnet wurde.

Das bedeutet: Für diese Wahl von B muss man die Werte der f_q durch die etwas größeren Werte 1,6 * f_q ersetzen, um die B-Potenzglattheit der p-1 zu erreichen.

In der Praxis legt man einen Wert für B fest, und schließt umgekehrt, für welche Werte von N diese Schranke ausreichend ist. Hierfür gilt:

$N \le B^{2 \frac{e}{e-1}} \approx B^{3.164}$

Gibt man sich also die Schranke B=10.000 vor, so lassen sich damit alle N behandeln, die kleiner oder gleich 4,5*10¹² sind.

Komplexität des Verfahrens

Aus der Abschätzung B ≥ N^0,316 ergibt sich eine Komplexität des Verfahrens von:

$O (\sqrt[3]{N} )$

Der Aufwand ist exponentiell in der Länge der Eingabe.

Anwendungen

Die Pollard-p-1-Methode wird unter anderem von GIMPS (Great Internet Mersenne Prime Search) verwendet, um Zahlen der Gestalt 2^p − 1 zu faktorisieren und damit die Anzahl der für die Suche nach Mersenne-Primzahlen notwendigen zeitaufwändigen Lucas-Lehmer-Tests verringern.

Literatur

G. Tenenbaum: Introduction to Analytic and Probabilistic Number Theory. S. 41, Th. 6.