Faktorisierungsverfahren
Pollard p-1
Theoretischer Hintergrund
Das (p-1)-Verfahren der Primfaktorisierung stammt von Pollard aus dem Jahre 1974.
Es ist ein probabilistisches Verfahren, das nur dann erfolgreich verläuft, wenn für ein Primteiler p einer
zusammengesetzten Zahl n, die Zahl p-1 das Produkt relativ kleiner Primfaktoren ist.
Genauer gilt: Falls (p,a)=1,
p|n und (p-1)|Q => p| ggt(aQ-1, n)
Das war zu erwarten, denn nach kleinem Fermat ist ap-1 = 1 mod p, daher aQ = 1 mod p.
Implementierung des Verfahrens
Man wählt eine Basis a teilerfremd zu n, und den maximalen Exponenten Q hinreichend gross.
Man bildet iterativ die Potenzen m=ak (mod n) mit k<=Q
in der Hoffnung, dass p|m-1, aber m-1 kein
Vielfaches von n ist. Dann ist 1 < ggt(n, m-1) < n ein Teiler von n.
Die Potenzen lassen sich wie folgt leicht berechnen:
ak! = (...((a1)2)...)k
Quellcode zu Pollard p-1:
INPUT n;
a = RANDOM(2,..n); m = a; g = 1; i = 1; k = 10000;
WHILE (i < k AND g = 1) DO
i=i+1;
m = mi mod n;
g = ggt(m-1, n);
ENDWHILE
IF 1 < g < n THEN ECHO "Primteiler gefunden: ". g;
Vor- und Nachteile von p-1
Das Problem besteht in der Praxis zum einen darin, dass man p nicht kennt, aber Q von p abhängt.
Setzten wir zum Beispiel Q=10000! = 2,8 * 1035660, dann werden i.a. Primteiler p von n gefunden,
für die p-1 = q1r1 * qsrs
mit qiri|Q, insbesondere qi<10000.
Das Verfahren kann also nicht garantieren, dass Primteiler gefunden werden, dafür ist es bei Erfolg schneller,
als eine systematische Suche.
Denn die theoretische Laufzeit ist O(q), wobei q der grösste Primteiler von p-1 ist, insbesondere
ist die Laufzeit nicht direkt von der Größe des Primteilers p von n abhängig.
Betrachten wir dazu ein Beispiel: N=1095+1
N = 1095 + 1
= 11 * 9091 * 1812604116731 * 121450506296081 * 909090909090909091 * 4996731930447843676185843959746621491531100801
Die kleinen Primfaktoren sind schnell gefunden, die anderen Primfaktoren finden wir unter folgenden Bedingungen:
Q=809!, weil 1812604116731 = 2 * 5 * 11 * ... * 809 + 1
Q=20509!, weil 121450506296081 = 24 * 5 * 13 ... * 20509 + 1
Q=333667!, weil 909090909090909091 = 2 * 34 * 5 * ... * 333667 + 1
Den letzen Primfaktor erhalten wir umsonst.
Big Prime Modifikation
Unser Vorgehen Q=k! ist numerisch ineffektiv.
Im obigen Beispiel sieht man, dass die höchsten Primteiler von p-1 nicht als Potenzen auftreten,
in Q aber kleine Primzahlpotenzen überrepräsentiert sind.
Bei der Berechnung einer oberen Schranke nimmt man besser
Q' = Q! * (pm*pm+1*...*pm+t)
d.h. alle höheren Primzahlen werden nur einfach bis zu einer zweiten Schranke berücksichtigt.
---
Literatur:
Bressoud, David M.: Factorization and Primality Testing. Springer, New-York 1989. S.67-74
Forster, Otto: Algorithmische Zahlentheorie. vieweg, Braunschweig 1996. S.113-122
Riesel, Hans: Prime Numbers and Computer Methods for Factorization. Birkhäuser 1994. S.172-173.