Pollard-p-1-Methode

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 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 \pmod{p}.

Ebenso gilt dann a^m \equiv 1 \pmod{p} für alle Vielfachen m von p-1. Das bedeutet, dass am-1 ein Vielfaches von p ist. Wenn nun N eine zu faktorisierende Zahl mit (unbekanntem) Primteiler p ist, teilt dieses p den 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[Bearbeiten]

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\left(p-1\right)} \leq B

Die Zahl eq(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) \leq \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 = \left\lfloor \frac{\log B}{\log q} \right\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 fq-mal vorkommt. Die Primzahlen in der Liste werden mit q1, q2, q3, ... , qR 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) 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_0=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 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[Bearbeiten]

Versagt das Verfahren in der 1. Phase, so liegt die Ursache oft darin, dass die 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 B1, um den Faktor l „einzufangen“. B1 sollte wesentlich größer als B gewählt werden, aber nicht größer als B2. Häufig wählt man B1 im Bereich von B4/3.

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

j_d = a_R^d (genauer: den Rest dieser Zahl modulo N)

Einerseits müssen hier nur wenige jd 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 di die Differenz zwischen der (i-1)-ten und der i-ten Primzahl in F1. 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 ggT(a_{R+i}-1,N) zu bilden. Stattdessen muss man die Zahlen aR+i-1 akkumulieren, d. h. man bildet das Produkt all dieser Zahlen. Das kann im Zuge der obigen Iteration mit erledigt werden, indem man z1=aR+1-1, und zi=zi-1*(aR+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 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 B1 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 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 m0.632 ist. Dieser Sachverhalt wird genutzt, um einen Wert für die Suchschranke B aus dem obigen Verfahren zu bestimmen.

Anwendung auf das Verfahren[Bearbeiten]

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\sqrt{N}. Nach der Heuristik gilt für den größten Primteiler q von p-1

q \le \left( p-1 \right)^{1-\frac{1}{e}} \le n^{\frac{1}{2}(1-\frac{1}{e})} \approx n^{0.316}

Wählt man also BN0,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 \left\lfloor \frac{e}{e-1} \frac{\log B}{\log q} \right\rfloor \approx 1,6 \cdot f_q

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

Das bedeutet: Für diese Wahl von B muss man die Werte der fq durch die etwas größeren Werte 1,6 * fq 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*1012 sind.

Komplexität des Verfahrens[Bearbeiten]

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

O (\sqrt[3]{N} )

Der Aufwand ist exponentiell in 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 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[Bearbeiten]

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