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 <math>2^p-1</math> 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 <math>p-1</math>-Faktorisierungsmethode von Pollard basiert auf dem kleinen fermatschen Satz. Sei <math>p</math> eine Primzahl, und <math>a</math> eine Zahl, die nicht von <math>p</math> geteilt wird, dann gilt

<math>a^{p-1} \equiv 1 \pmod{p}</math>.

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

Die 1. Phase des Verfahrens

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

<math>q^{e_q\left(p-1\right)} \leq B</math>

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

<math>e_q\left( m \right) \leq \frac{\log B}{\log q}</math>

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

<math>f_q = \left\lfloor \frac{\log B}{\log q} \right\rfloor</math>

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

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

Dabei werden in jedem Schritt die auftretenden Potenzen durch ihre Reste modulo <math>N</math> 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 <math>\operatorname{ggT}(a_{20}-1,N)</math>. 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 <math>a_R=a^M</math> erreicht hat.

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

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

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

Analog zur ersten Phase erstellt man die Liste <math>F_1</math> der Primzahlen die zwischen <math>B</math> und <math>B_1</math> liegen. Dabei speichert man die erste dieser Zahlen als <math>l_1</math> und trägt in die Liste die Differenzen zwischen benachbarten Primzahlen ein. Die Anzahl der Elemente von <math>F_1</math> sei <math>S</math>. Beachte: Für <math>B_1< 20.000.000</math> 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 <math>a_R</math>, welche am Ende der 1. Phase berechnet wurde. Als weitere Vorbereitung berechnet man für jede Differenz <math>d</math> in <math>F_1</math> die Zahl

<math>j_d = a_R^d</math> (genauer: den Rest dieser Zahl modulo <math>N</math>)

Einerseits müssen hier nur wenige <math>j_d</math> 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.

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

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

Nach einer festen Anzahl von Schritten, etwa wieder jedem 20., bildet man <math>\operatorname{ggT}(z_i,N)</math>. 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 <math>B</math> und <math>B_1</math> 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 <math>m</math> hat im Durchschnitt <math>\log \log m</math> Primteiler. Diese Aussage lässt sich präzise formulieren und beweisen. Man tut so, als hätte die Anzahl der Primteiler von <math>m</math> genau diesen Wert, d. h., man nimmt an, dass

<math>\omega \left( m \right) = \log \log m</math>

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

<math>\omega \left( \frac{m}{q} \right) = \omega(m)-1</math>

Auflösen dieser Gleichung nach <math>q</math> liefert:

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

Anwendung auf das Verfahren

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

<math>q \le \left( p-1 \right)^{1-\frac{1}{e}} \le n^{\frac{1}{2}(1-\frac{1}{e})} \approx n^{0{,}316}</math>

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

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

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

Die Zahl <math>f_q</math> ist hier dieselbe, die in der 1. Phase berechnet wurde.

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

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

<math>N \le B^{2 \frac{e}{e-1}} \approx B^{3{,}164}</math>

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

Komplexität

Aus der Abschätzung <math>B\ge N^{0{,}316}</math> ergibt sich eine Komplexität des Verfahrens von:

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.