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 $\operatorname {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_{1},q_{2},q_{3},\ldots ,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) $\operatorname {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_{1}=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 $\operatorname {ggT} (a_{20}-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 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_{1}$, um den Faktor $l$ „einzufangen“. $B_{1}$ sollte wesentlich größer als $B$ gewählt werden, aber nicht größer als $B^{2}$. Häufig wählt man $B_{1}$ im Bereich von $B^{\frac {4}{3}}$.

Analog zur ersten Phase erstellt man die Liste $F_{1}$ der Primzahlen die zwischen $B$ und $B_{1}$ liegen. Dabei speichert man die erste dieser Zahlen als $l_{1}$ und trägt in die Liste die Differenzen zwischen benachbarten Primzahlen ein. Die Anzahl der Elemente von $F_{1}$ sei $S$. Beachte: Für $B_{1}<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_{1}$ 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_{1}$. 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 $\operatorname {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_{1}=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 $\operatorname {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_{1}$ 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\leq {\sqrt {N}}$. Nach der Heuristik gilt für den größten Primteiler $q$ von $p-1$

$q\leq \left(p-1\right)^{1-{\frac {1}{e}}}\leq n^{{\frac {1}{2}}(1-{\frac {1}{e}})}\approx n^{0{,}316}$

Wählt man also $B\geq 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)}\leq n^{\frac {1}{2}}\leq 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)\leq \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\cdot 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\leq 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\cdot 10^{12}$ sind.

Komplexität des Verfahrens

Aus der Abschätzung $B\geq N^{0{,}316}$ ergibt sich eine Komplexität des Verfahrens von:

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

Der Aufwand wächst exponentiell mit 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 zu verringern.

Literatur

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