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.

Anwendungen

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

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(\mathrm{mod}p)$.

Ebenso gilt dann $a^m\equiv 1(\mathrm{mod}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 $\mathrm{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(p-1)}\le 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)\le \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=\lfloor \frac{\log B}{\log q}\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,\dots ,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) $\mathrm{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 $\mathrm{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 $\mathrm{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 $\mathrm{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\le \sqrt{N}$. Nach der Heuristik gilt für den größten Primteiler $q$ von $p-1$

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

Wählt man also $B\ge 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 \lfloor \frac{e}{e-1}\frac{\log B}{\log q}\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\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\cdot 10^{12}$ sind.

Komplexität

Aus der Abschätzung $B\ge 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.

Literatur

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