Pollard-p − 1-Methode

Die Pollard-p − 1-Methode i​st ein Verfahren z​ur Faktorisierung v​on zusammengesetzten Zahlen. Sie w​urde 1974 v​on John M. Pollard beschrieben.

Mathematische Grundlagen

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

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

Ebenso gilt dann ${\displaystyle a^{m}\equiv 1{\pmod {p}}}$ für alle Vielfachen ${\displaystyle m}$ von ${\displaystyle p-1}$. Das bedeutet, dass ${\displaystyle a^{m}-1}$ ein Vielfaches von ${\displaystyle p}$ ist. Wenn nun ${\displaystyle N}$ eine zu faktorisierende Zahl mit (unbekanntem) Primteiler ${\displaystyle p}$ ist, teilt dieses ${\displaystyle p}$ den ${\displaystyle \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 ${\displaystyle N}$. Im folgenden Absatz wird eine Methode beschrieben, wie man eine passende Zahl ${\displaystyle m}$ finden kann.

Die 1. Phase des Verfahrens

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

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

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

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

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

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

Das ist der größte ${\displaystyle q}$-Exponent, den eine ${\displaystyle B}$-potenzglatte Zahl ${\displaystyle m}$ haben kann. Man erstellt als Nächstes eine Liste ${\displaystyle F}$, in welcher die Primzahl ${\displaystyle q}$ genau ${\displaystyle f_{q}}$-mal vorkommt. Die Primzahlen in der Liste werden mit ${\displaystyle q_{1},q_{2},q_{3},\ldots ,q_{R}}$ durchnummeriert, wobei ${\displaystyle R}$ die Anzahl der Listenelemente von ${\displaystyle F}$ ist. Das Produkt aller Zahlen in ${\displaystyle F}$ wird mit ${\displaystyle M}$ bezeichnet. Nach Konstruktion ist ${\displaystyle M}$ ${\displaystyle B}$-potenzglatt. Es ist sogar die größte ${\displaystyle B}$-potenzglatte Zahl.

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

${\displaystyle a_{1}=a}$

${\displaystyle a_{i+1}=a_{i}^{q_{i}}}$ für ${\displaystyle i=1,...,R}$

Dabei werden in jedem Schritt die auftretenden Potenzen durch ihre Reste modulo ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle a_{R}=a^{M}}$ erreicht hat.

Insgesamt können a​m Ende d​rei Fälle auftreten:

1. Man findet einen echten Teiler von ${\displaystyle N}$. In diesem Fall war das Verfahren erfolgreich, und man hat ${\displaystyle N}$ in zwei Faktoren zerlegt. Gegebenenfalls kann man das Verfahren erneut auf diese beiden Zahlen anwenden, bis man die Primfaktorzerlegung von ${\displaystyle N}$ erhält, oder für einen der Faktoren von ${\displaystyle N}$ Fall 3 auftritt.
2. Man findet den Teiler ${\displaystyle N}$ von ${\displaystyle N}$. Dieser Fall ist nicht besonders wahrscheinlich, kann aber auftreten. In diesem Fall ist es ratsam, einen anderen Wert für ${\displaystyle a}$ zu wählen.
3. Man findet den Teiler 1 von ${\displaystyle N}$. In diesem Fall war die Annahme, dass es einen Teiler ${\displaystyle p}$ von ${\displaystyle N}$ gibt, für den ${\displaystyle p-1}$ ${\displaystyle B}$-potenzglatt ist, falsch. In diesem Fall sollte man die 2. Phase der ${\displaystyle 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 ${\displaystyle p}$ von ${\displaystyle N}$ gilt, dass ${\displaystyle p-1=u\cdot l}$. Dabei ist ${\displaystyle u}$ B-glatt oder sogar B-potenzglatt, und ${\displaystyle l}$ eine Primzahl, die größer als ${\displaystyle B}$ ist. Mit anderen Worten: ${\displaystyle p-1}$ ist nur wegen eines einzigen Primfaktors nicht B-(potenz-)glatt.

Man wählt daher eine zweite Schranke ${\displaystyle B_{1}}$, um den Faktor ${\displaystyle l}$ „einzufangen“. ${\displaystyle B_{1}}$ sollte wesentlich größer als ${\displaystyle B}$ gewählt werden, aber nicht größer als ${\displaystyle B^{2}}$. Häufig wählt man ${\displaystyle B_{1}}$ im Bereich von ${\displaystyle B^{\frac {4}{3}}}$.

Analog zur ersten Phase erstellt man die Liste ${\displaystyle F_{1}}$ der Primzahlen die zwischen ${\displaystyle B}$ und ${\displaystyle B_{1}}$ liegen. Dabei speichert man die erste dieser Zahlen als ${\displaystyle l_{1}}$ und trägt in die Liste die Differenzen zwischen benachbarten Primzahlen ein. Die Anzahl der Elemente von ${\displaystyle F_{1}}$ sei ${\displaystyle S}$. Beachte: Für ${\displaystyle 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 ${\displaystyle a_{R}}$, welche am Ende der 1. Phase berechnet wurde. Als weitere Vorbereitung berechnet man für jede Differenz ${\displaystyle d}$ in ${\displaystyle F_{1}}$ die Zahl

${\displaystyle j_{d}=a_{R}^{d}}$ (genauer: den Rest dieser Zahl modulo ${\displaystyle N}$)

Einerseits müssen hier nur wenige ${\displaystyle 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.

${\displaystyle a_{R+1}=a_{R}^{l_{1}}}$

${\displaystyle 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 ${\displaystyle i=2,3,...,S}$

Dabei sei ${\displaystyle d_{i}}$ die Differenz zwischen der ${\displaystyle (i-1)}$-ten und der ${\displaystyle i}$-ten Primzahl in ${\displaystyle F_{1}}$. Wiederum ersetzt man die Zahlen in jedem Schritt durch ihre Reste modulo ${\displaystyle N}$.

Anders als in Phase 1 reicht es nicht aus, nach einer festen Anzahl von Schritten den ${\displaystyle \operatorname {ggT} (a_{R+i}-1,N)}$ zu bilden. Stattdessen muss man die Zahlen ${\displaystyle 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 ${\displaystyle z_{1}=a_{R+1}-1}$, und ${\displaystyle z_{i}=z_{i-1}(a_{R+i}-1)}$ setzt. Durch das Akkumulieren erreicht man, dass auch Primfaktoren ${\displaystyle p}$ von ${\displaystyle N}$ gefunden werden können, bei denen mehr als ein Primfaktor von ${\displaystyle p-1}$ größer als ${\displaystyle B}$ ist.

Nach einer festen Anzahl von Schritten, etwa wieder jedem 20., bildet man ${\displaystyle \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 ${\displaystyle B}$ und ${\displaystyle 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 ${\displaystyle m}$ hat im Durchschnitt ${\displaystyle \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 ${\displaystyle m}$ genau diesen Wert, d. h. man nimmt an, dass

${\displaystyle \omega \left(m\right)=\log \log m}$

Es sei nun ${\displaystyle q}$ der größte Primteiler von ${\displaystyle m}$. Dann gilt:

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

Auflösen dieser Gleichung nach ${\displaystyle q}$ liefert:

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

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

Anwendung auf das Verfahren

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

${\displaystyle 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 ${\displaystyle B\geq N^{0{,}316}}$, so ist zu erwarten, dass ${\displaystyle p-1}$ ${\displaystyle B}$-glatt ist. Die ${\displaystyle B}$-Potenzglattheit lässt sich nun so erreichen: Angenommen ${\displaystyle p-1}$ sei ${\displaystyle B}$-glatt. Dann gilt für alle Primteiler ${\displaystyle q}$ von ${\displaystyle p-1}$:

${\displaystyle 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 ${\displaystyle B}$-potenzglatte Zahl ${\displaystyle m}$:

${\displaystyle 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 ${\displaystyle f_{q}}$ ist hier dieselbe, die in der 1. Phase berechnet wurde.

Das bedeutet: Für diese Wahl von ${\displaystyle B}$ muss man die Werte der ${\displaystyle f_{q}}$ durch die etwas größeren Werte ${\displaystyle 1{,}6\cdot f_{q}}$ ersetzen, um die ${\displaystyle B}$-Potenzglattheit der ${\displaystyle p-1}$ zu erreichen.

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

${\displaystyle N\leq B^{2{\frac {e}{e-1}}}\approx B^{3{,}164}}$

Gibt man sich also die Schranke ${\displaystyle B=10.000}$ vor, so lassen sich damit alle ${\displaystyle N}$ behandeln, die kleiner oder gleich ${\displaystyle 4{,}5\cdot 10^{12}}$ sind.

Komplexität des Verfahrens

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

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

Der Aufwand wächst exponentiell m​it der Länge d​er Eingabe.

Anwendungen

Die Pollard-p − 1-Methode wird unter anderem von GIMPS (Great Internet Mersenne Prime Search) verwendet, um Zahlen der Gestalt ${\displaystyle 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.