Berechnungsverfahren
Pollards p-1-Methode
Im Folgenden lernen Sie die p-1-Methode von J. Pollard kennen, mit der Sie einen Faktor f einer natürlichen Zahl n bestimmen können. Diese Methode funktioniert allerdings nur dann, wenn n einen Primfaktor p enthält, derart dass p-1 aus hinreichend kleinen Primfaktorpotenzen besteht.
Beispiel:
| n = | 7935104802863525901487 = p · q |
| p = | 80768455531 |
| p-1 = | 80768455530 = 2 · 3 · 5 · 7 · 41 · 997 · 972 |
Alle Primfaktorpotenzen, aus denen p-1 besteht, sind kleiner als b = 10000 (die größte ist 972 = 9409). In diesem Fall funktioniert also die p-1-Methode.
Idee
Die zu faktorisierende Zahl n ist ein Vielfaches einer Primzahl p. Ist nun eine Zahl m ebenfalls ein Vielfaches von p, so gilt
p | ggt(m, n).
Sofern ggt(m, n) ≠ n ist, haben Sie einen Faktor von n gefunden.
Ohne p zu kennen, begeben Sie sich nun auf die Suche nach einer solchen Zahl m, die ein Vielfaches von p ist.
Behauptung: Sei p > 2 eine Primzahl. Wenn k ein Vielfaches von p-1 ist, so ist 2k-1 ein Vielfaches von p.
Beispiel: Sei p = 5. Dann ist z.B. 12 ein Vielfaches von p-1, und es gilt 212-1 = 4096-1 ist Vielfaches von 5.
Beweis: Nach dem kleinen Satz von Fermat gilt für jede Primzahl p > 2
2p-1 ≡ 1 (mod p).
Wenn k ein Vielfaches von p-1 ist, etwa k = (p-1)·r, so gilt
2k ≡ 2(p-1)·r ≡ 1r ≡ 1 (mod p).
Dies aber bedeutet nach Definition von ≡
p | 2k-1,
d.h. 2k-1 ist ein Vielfaches von p.
Wenn p-1 nur aus Primfaktorpotenzen < b besteht, so finden Sie ein Vielfaches k von p-1, indem Sie alle Primzahlpotenzen < b miteinander multiplizieren:
k = 
q prim, qe<b, e maximal qe
Dann aber ist m = 2k-1 das gesuchte Vielfache von p. Damit gilt p | ggt(m, n), und sofern ggt(m, n) ≠ n ist, haben Sie einen Faktor von n gefunden.
Implementierung: modulo n rechnen
Ist die Grenze b groß, etwa 104, so wird die Zahl k sehr groß, und natürlich erst recht die Zahl 2k-1. Zum Glück lässt sich jedoch vermeiden, dass die Zahlen über alle Maßen groß werden.
Es gilt nämlich
ggt(m, n) = ggt(m mod n, n).
Mit m = 2k-1 gilt
m mod n = (2k-1) mod n = 2k mod n – 1
Statt 2k berechnen Sie also 2k mod n. Da k ein Produkt von Zahlen k0, ..., ks-1 ist, erhalten Sie 2k mod n als wiederholte modulare Exponentiation:
v = 2k mod n = (...((2k0 mod n)k1 mod n) ... )ks-1 mod n.
Um den Fall auszuschließen, dass ggt(m, n) = n ist, prüfen Sie nach jeder modularen Exponentiation in dem obigen Ausdruck, ob ggt(v-1, n) ≠ 1 ist. Ist dies der Fall, so haben Sie einen Faktor f von n mit
f = ggt(v-1, n)
gefunden.
Programm
Es folgt eine Implementierung der p-1-Methode in Python.
Pollardp-1.py
# (Sieb des Eratosthenes)
def allPrimes(b):
s=[True]*b
p=[]
for i in range(2, b):
if s[i]:
p+=[i]
for j in range(i*i, b, i):
s[j]=False
return p
# liefert die hoechste Potenz von q, die kleiner als b ist
def highestPower(q, b):
z=q
while z*q<b:
z*=q
return z
# berechnet v = 2 hoch k mod n, wobei k = k0 * k1 * ... * kr;
# hierbei sind die ki die hoechsten Potenzen der
# Primzahlen pi, die kleiner als b sind;
# nach jeder modularen Exponentiation wird geprueft,
# ob ggt(v-1, n) = 1 ist -
# wenn nicht, so ist ein Faktor f gefunden
def factorOf(b, n):
v=2
for p in allPrimes(b):
k=highestPower(p, b)
v=modexp(v, k, n)
f=ggt(v-1, n)
if f!=1:
return f
return f
# Hauptprogramm
if __name__=="__main__":
from BasicFunctions import *
b=10000
# Test 1:
n=7935104802863525901487
print(n)
f=factorOf(b, n)
print(f)
assert f==80768455531
print("Ok")
# Test 2:
n=19*997
print(n)
f=factorOf(b, n)
print(f)
assert f==19
print("Ok")
Die Funktionen ggt zur Berechnung des größten gemeinsamen Teilers und modexp zur schnellen Exponentiation importieren Sie aus dem Python-Modul BasicFunctions.
Literatur
[Bu 00] J.A. Buchmann: Introduction to Cryptography. Springer (2000)
[Lan 23] H.W. Lang: Kryptografie für Dummies. 2. Auflage, Wiley (2023)
Weiter mit: [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 05.12.2016 Updated: 05.05.2025
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden