Zahlentheoretische Algorithmen der Kryptografie

Pollards p-1-Methode

 aufwärts

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 Primfaktor­potenzen besteht.

Beispiel:  

n  =  7935104802863525901487  =  p · q
p  =  80768455531
p-1  =  80768455530  =  2 · 3 · 5 · 7 · 41 · 997 · 972

Alle Primfaktor­potenzen, 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  kongruent 1   (mod p).

Wenn k ein Vielfaches von p-1 ist, etwa k = (p-1)·r, so gilt

2k  kongruent  2(p-1)·r  kongruent  1r  kongruent  1   (mod p).

Dies aber bedeutet nach Definition von  kongruent 

p | 2k-1,

d.h. 2k-1 ist ein Vielfaches von p.

 

Wenn p-1 nur aus Primfaktor­potenzen < b besteht, so finden wir ein Vielfaches k von p-1, indem wir alle Primzahl­potenzen < b miteinander multi­plizieren:

k  =  Produkt 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   kongruent   (2k-1) mod n   kongruent   2k mod n – 1 mod n   kongruent   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
# liefert eine Liste aller Primzahlen kleiner als h
# (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 GgtIterativ import ggt
    from ModExp import modexp
    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)

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 05.12.2016   Updated: 26.02.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik