Berechnungsverfahren
Pollards p-1-Methode
Im Folgenden wird die p-1-Methode von J. Pollard zur Bestimmung eines Primfaktors p einer ganzen Zahl n dargestellt. Diese Methode funktioniert nur dann, wenn 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 wir einen Faktor von n gefunden.
Ohne p zu kennen, begeben wir uns 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 wir ein Vielfaches k von p-1, indem wir alle Primzahlpotenzen < b miteinander multiplizieren:
k = 
q prim, qe<b, e maximal qe
Dann aber ist m = 2k-1 das gesuchte Vielfache von p und f = ggt(m, n) ist ein Faktor von n.
Implementierung
Ist die Grenze b groß, etwa 109, 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 mod n ≡ 2k mod n – 1 (mod n).
Da 2k mod n ≠ 0 ist, gilt anstelle der Kongruenz modulo n sogar die Gleichheit.
Statt 2k berechnen wir also 2k mod n. Da k ein Produkt von Zahlen k0, ..., ks-1 ist, ergibt sich 2k mod n als wiederholte modulare Exponentiation:
v = 2k mod n = (...((2k0 mod n)k1 mod n) ... )ks-1 mod n.
Nun ergibt sich ein Faktor f der Zahl n durch
f = ggt(v-1, n).
Programm
Es folgt eine Implementierung der p-1-Methode in Python.
Pollardp-1.py
# (Sieb des Eratosthenes)
def allPrimes(h):
s=[True]*h
p=[]
for i in range(2, h):
if s[i]:
p+=[i]
for j in range(i*i, h, i):
s[j]=False
return p
# liefert die hoechste Potenz von q, die kleiner als h ist
def highestPower(q, h):
z=q
while z*q<h:
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 h sind
def powerOfTwo(h, n):
v=2
for p in allPrimes(h):
k=highestPower(p, h)
v=modexp(v, k, n)
return v
# berechnet einen Faktor von n, sofern p-1 nur aus
# Primfaktorpotenzen besteht, die kleiner als h sind
def factorOf(h, n):
m=powerOfTwo(h, n)-1
f=ggt(m, n)
return f
if __name__=="__main__":
from BasicFunctions import *
h=10000
n=7935104802863525901487
print n
f=factorOf(h, n)
print f
assert f==80768455531
print "Ok"
Die Funktionen ggt zur Berechnung des größten gemeinsamen Teilers und modexp zur schnellen Exponentiation werden importiert.
Literatur
[Bu 00] J.A. Buchmann: Introduction to Cryptography. Springer (2000)
[Lan 18] H.W. Lang: Kryptografie für Dummies. Wiley (2018)
Weiter mit: [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 05.12.2016 Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden