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

.

Ebenso gilt dann für alle Vielfachen von . Das bedeutet, dass ein Vielfaches von ist. Wenn nun eine zu faktorisierende Zahl mit (unbekanntem) Primteiler ist, teilt dieses den , da es beide Zahlen teilt, von denen der ggT gebildet wurde. Meist ist dieser ggT ein echter Teiler von . Im folgenden Absatz wird eine Methode beschrieben, wie man eine passende Zahl finden kann.

Die 1. Phase des Verfahrens

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

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

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

Das ist der größte -Exponent, den eine -potenzglatte Zahl haben kann. Man erstellt als Nächstes eine Liste , in welcher die Primzahl genau -mal vorkommt. Die Primzahlen in der Liste werden mit durchnummeriert, wobei die Anzahl der Listenelemente von ist. Das Produkt aller Zahlen in wird mit bezeichnet. Nach Konstruktion ist -potenzglatt. Es ist sogar die größte -potenzglatte Zahl.

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

für

Dabei werden in jedem Schritt die auftretenden Potenzen durch ihre Reste modulo 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 . 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 erreicht hat.

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

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

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

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

(genauer: den Rest dieser Zahl modulo )

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

für

Dabei sei die Differenz zwischen der -ten und der -ten Primzahl in . Wiederum ersetzt man die Zahlen in jedem Schritt durch ihre Reste modulo .

Anders als in Phase 1 reicht es nicht aus, nach einer festen Anzahl von Schritten den zu bilden. Stattdessen muss man die Zahlen akkumulieren, d. h. man bildet das Produkt all dieser Zahlen. Das kann im Zuge der obigen Iteration mit erledigt werden, indem man , und setzt. Durch das Akkumulieren erreicht man, dass auch Primfaktoren von gefunden werden können, bei denen mehr als ein Primfaktor von größer als ist.

Nach einer festen Anzahl von Schritten, etwa wieder jedem 20., bildet man . 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 und 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 hat im Durchschnitt Primteiler. Diese Aussage lässt sich präzise formulieren und beweisen. Man tut so als hätte die Anzahl der Primteiler von genau diesen Wert, d. h. man nimmt an, dass

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

Auflösen dieser Gleichung nach liefert:

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

Anwendung auf das Verfahren

Sei nun eine zusammengesetzte natürliche Zahl, auf die man die -Methode anwenden möchte. Da sie zusammengesetzt ist, besitzt sie einen Primteiler . Nach der Heuristik gilt für den größten Primteiler von

Wählt man also , so ist zu erwarten, dass -glatt ist. Die -Potenzglattheit lässt sich nun so erreichen: Angenommen sei -glatt. Dann gilt für alle Primteiler von :

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

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

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

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

Gibt man sich also die Schranke vor, so lassen sich damit alle behandeln, die kleiner oder gleich sind.

Komplexität des Verfahrens

Aus der Abschätzung ergibt sich eine Komplexität des Verfahrens von:

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 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.