Pollard-p − 1-Methode

Verfahren zur Faktorisierung zusammengesetzter Zahlen

Die Pollard-p − 1-Methode ist ein Verfahren zur Faktorisierung von zusammengesetzten Zahlen. Sie wurde 1974 von John M. Pollard beschrieben.

Mathematische Grundlagen

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

 

Der Aufwand wächst exponentiell mit der Länge der Eingabe.

Anwendungen

Bearbeiten

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

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