<< . .

. 25
( : 33)



. . >>

Beim RSA-Verfahren werden zwei (große) Primzahlen p und q miteinander mul-
tipliziert, was sehr einfach ist. Die Zahl N = p q jedoch wieder in ihre Prim-
teiler zu faktorisieren wird als außerordentlich schwierig angesehen. Dabei ist
aber nicht bekannt, ob das Problem der Faktorisierung tats¤chlich schwierig ist. Es
könnte ja durchaus auch sein, daß es eine einfache Methode gibt, Zahlen in ihre
Primfaktoren zu zerlegen, diese bisher nur noch nicht bekannt ist. Kurz gesagt,
das Problem ist in NP , aber es ist nicht bekannt, ob es vielleicht in P liegt.
Neben der (naiven) Probedivision, bei der man einfach sukzessive N durch be-
kannte (aber kleine) Primzahlen teilt, gibt es ausgefeilte Methoden, von denen
wir einige in diesem Kapitel vorstellen. Dabei konzentrieren wir uns nicht auf
Zahlen N, die Produkt von zwei Primzahlen sind, wie es beim RSA-Verfahren
verwendet wird. Wir behandeln das Problem der Zerlegung, d. h. der Faktorisie-
rung ganzer (zusammengesetzter) Zahlen allgemein.
Die Methoden, die man dabei benutzt, greifen zum Teil bekannte Verfahren auf.
Wir werden Pollards -Methode erneut ins Spiel bringen, mit dessen Hilfe wir be-
reits diskrete Logarithmen berechnet haben, und die Kettenbrüche, mit deren Hilfe
wir einen Angriff auf RSA geschildert haben, werden wieder eine Rolle spielen.
Weiter werden wir das Verfahren von Fermat, das quadratische Sieb wie auch die
p ’ 1 -Methode von Pollard behandeln. Die Idee der letztgenannten Methode von
Pollard l¤sst sich auf elliptische Kurven übertragen. Damit gewinnt man die el-
liptic curve method, die wir aber erst nach der Einführung von elliptischen Kurven
im letzten Kapitel 14 behandeln werden.



11.1 Prinzipielles Vorgehen

Gegeben ist eine natürliche Zahl N. Nach dem Fundamentalsatz 4.14 der Arith-
metik besitzt N von der Reihenfolge der Faktoren abgesehen genau eine Zerle-
gung in Primzahlen:
N = p1 · · · p n ,

wobei die Primzahlen p1 , . . . , pn nicht verschieden sein müssen. Um die Prim-
zahlen p1 , . . . , pn zu bestimmen, suchen wir nach einem nichttrivialen Teiler d
von N. Gegebenenfalls wird das Verfahren auf d und N erneut angewendet.
d
Wir beschr¤nken uns stets darauf zu beschreiben, wie d gefunden werden kann.
Wir sagen dann, wir h¤tten eine Zerlegung für N gefunden oder N sei zerlegt
192 11 Faktorisierung

oder “ etwas schlampig “ N sei faktorisiert. Um eine Zerlegung von N zu bestim-
men, hat sich das folgende Vorgehen bew¤hrt.

Prüfe, ob N durch eine Primzahl p kleiner einer festgelegten Schranke B teilbar
ist.

Dazu bestimmt man (oder hat schon gespeichert) eine Liste aller Primzahlen
¤ B und berechnet sukzessive den Rest von N bei Division durch p. Ist er 0
wird p ausgegeben “ Stop!
Will man nur wissen, ob solche Primteiler existieren, berechnet man d =
ggT(R, N), wobei R Produkt aller Primzahlen ¤ B ist. Diese Vorgehenswei-
se ist insbesondere dann vorteilhaft, wenn nicht damit gerechnet werden
muss, dass es solche Primzahlen gibt.

Falls keine solchen Primteiler gefunden werden:

Prüfe, ob N eine Primzahl ist (vgl. Kapitel 8 über Primzahltests). Falls ja “
Stop!; falls nein:

Prüfe, ob N Potenz einer natürlichen Zahl ist (vgl. Aufgabe 8.6). Falls ja “ Stop!;
falls nein:

Erst jetzt bringt man die schweren Geschütze ins Spiel, die wir in den folgen-
den Abschnitten besprechen. Dabei emp¬ehlt sich im Allgemeinen die Rei-
henfolge (wobei nicht alle Verfahren angewendet werden müssen):

p ’ 1 -Methode mit kleiner Schranke B,
Pollards -Methode,
Kettenbruchmethode,
die elliptische Kurven Methode nach Lenstra (siehe Abschnitt 14.3),
quadratisches Sieb,
Zahlkörpersieb.

Bemerkung
Das Zahlkörpersieb werden wir in diesem Buch nicht behandeln, es sind hierzu
weit mehr Hilfsmittel aus der Algebra nötig als wir zur Verfügung haben.

Die Schranke B, bis zu der Probedivisionen durchgeführt werden, h¤ngt sehr von
der Anwendung ab. MAPLE benutzt B = 100 000, Cohen [7] schl¤gt B = 500 000
vor und diskutiert größere Schranken.
Für den Rest dieses Kapitels setzen wir N als zusammengesetzte natürliche Zahl
voraus, d. h. N ist ungleich 1 und keine Primzahl. Unser Ziel ist es, einen nicht-
trivialen Teiler d von N zu ¬nden.
11.2 Pollards -Methode * 193

11.2 Pollards -Methode *

Bei der Bestimmung diskreter Logorithmen haben wir neben dem Baby-Step-
Giant-Step-Algorithmus Pollards -Methode in Abschnitt 10.3 beschrieben. Bei
der Methode von Pollard wurde eine (unendliche) Zufallsfolge (xi ) in einer end-
lichen Menge gebildet. Dass es bei einer solchen Folge Indizes i = j mit xi = x j
gibt, ist klar “ wir nennen ein solches Tripel (xi = x j , i, j) einen Treffer “, der
Clou an der Methode war, dass ein solcher Treffer relativ schnell bestimmt wer-
den kann. In diesem Sinne ist Pollards -Methode ein Suchalgorithmus, der aus
einer (unendlichen) Folge (xi ) in einer endlichen Menge einen Treffer bestimmt.
Wir können diesen Algorithmus auch für andere Probleme benutzen, etwa zum
Bestimmen von Teilern einer natürlichen Zahl.



11.2.1 Die Idee

Die zusammengesetzte natürliche Zahl N wird von einer “ uns unbekannten “
Primzahl p geteilt. Wir suchen zwei ganze Zahlen x und y mit

x ≡ y (mod N) und x ≡ y (mod p) .

Angenommen, wir haben solche Zahlen x und y gefunden. Es ist dann

d = ggT(x ’ y, N)

ein nichttrivialer Teiler von N, da:

Aus p | x ’ y und p | N folgt p | d, sodass d = 1 gilt, und


aus N x ’ y folgt d = N.


Wie oben bemerkt ist dann eine Zerlegung von N gefunden, auf die der Algorith-
mus ggf. erneut angewendet werden kann.



11.2.2 Konstruktion der Zahlen x und y

Die Zahlen x und y ¬nden wir mit dem Algorithmus von Pollard. Dabei bilden
wir im Wesentlichen in der endlichen Menge Z p , wobei p ein unbekannter Prim-
teiler von N ist, eine (unendliche) Folge (xi ). Für einen Treffer gilt dann die ge-
wünschte Kongruenz:

xi ≡ x j (mod p) , d. h. d = ggT(xi ’ x j , N) > 1 .

Gilt zudem die Inkongruenz xi ≡ x j (mod N), so folgt d = N.
194 11 Faktorisierung

Wir de¬nieren die Zahlenfolge (xi ) rekursiv mit einer Abbildung f (x) = x2 + c,
wobei c ∈ Z \ {0, ’2} (siehe Aufgabe 11.1), und einem Startwert x0 :

xi+1 = f (xi ) .

Diese spezielle Wahl von f hat sich in der Praxis bew¤hrt, h¤u¬g wird c = 1
gew¤hlt. Im folgenden Algorithmus benutzen wir Lemma 10.2, um einen nicht-
trivialen Teiler d von N zu bestimmen.

W¤hle ein x0 ∈ {0, . . . , N ’ 1} und ein c ∈ Z \ {0, ’2}.

Berechne x1 = f (x0 ) und x2 = f ( f (x0 )) modulo N.

Falls 1 < d = ggT(x2 ’ x1 , N), Stop!, sonst:

Berechne x2 = f (x1 ) und x4 = f ( f (x2 )) modulo N.

Falls 1 < d = ggT(x4 ’ x2 , N), Stop!, sonst:

Berechne x3 = f (x2 ) und x6 = f ( f (x4 )) modulo N.

Falls 1 < d = ggT(x6 ’ x3 , N), Stop!, usw.

Der Algorithmus terminiert nach Lemma 10.2. In dem seltenen Fall d = N, in
dem nichts gewonnen ist, w¤hle man ein neues c und starte erneut. Die Wahl
eines neuen Starwertes x0 emp¬elt sich nicht. Der Fall d = N tritt ein, wenn für
alle Primteiler von N gleichzeitig Treffer auftreten.

Beispiel
Wir suchen einen nichttrivialen Teiler der (zusammengesetzten) Zahl N = 1 517.
Für c w¤hlen wir 1, d. h. f (x) = x2 + 1, und als Startwert w¤hlen wir x0 = 70.

= 350 x2 = 1141 ggT(1141 ’ 350, 1517) = 1
x1
= 1141 x4 = 1148 ggT(1148 ’ 1141, 1517) = 1
x2
= 296 x6 = 412 ggT(412 ’ 296, 1517) = 1
x3
= 1148 x8 = 1010 ggT(1010 ’ 1148, 1517) = 1
x4
= 1149 x10 = 196 ggT(196 ’ 1149, 1517) = 1
x5
= 412 x12 = 862 ggT(862 ’ 412, 1517) = 1
x6
= 1358 x14 = 825 ggT(825 ’ 1358, 1517) = 41
x7

Damit ist 1 517 = 37 · 41 zerlegt.


Pollards p ’ 1-Methode
11.3

Mit der p ’ 1-Methode ¬ndet man Primteiler p von N, für die p ’ 1 Produkt von
kleinen Primzahlen ist. Dabei spielt die Größe von p kaum eine Rolle.
11.3 Pollards p ’ 1-Methode 195

11.3.1 Die Methode

Es sei p ein “ uns unbekannter “ Primteiler von N, also N = p m mit m ∈ N >1 .
Ist a eine zu N teilerfremde natürliche Zahl, so ist a auch zu p teilerfremd. Nach
dem Satz 6.10 von Fermat gilt

a p’1 ≡ 1 (mod p) .

Jedes Vielfache k von p ’ 1 erfüllt dann ebenfalls

ak ≡ 1 (mod p) , d. h. p | ak ’ 1 .

Wegen p | ak ’ 1 liefert der euklidische Algorithmus eine Zahl d mit

p | d = ggT(ak ’ 1, N) .

Ist d = N, so ist N zerlegt. Diese p ’ 1 -Methode von Pollard ist dann sinnvoll,
wenn p ’ 1 ein Produkt von kleinen Primzahlen ist. Man w¤hlt für k das Produkt
aller Primzahlpotenzen unterhalb einer vorgegebenen Schranke B und ¬ndet so
ein Vielfaches k von p ’ 1, d. h.,

∏ qe ,
k = »(B) = kgV(1, . . . , B) = wobei qe ¤ B .
q∈P




11.3.2 Glatte Zahlen

Es sei B ∈ N. Eine Zahl m ∈ N heißt B -glatt, wenn jede Primzahl p, die m teilt,
kleiner gleich B ist:
p | m ’ p ¤ B.

Die Zahl m heißt B -potenzglatt, wenn jede Primzahlpotenz pν , die m teilt, kleiner
gleich B ist:
pν | m ’ pν ¤ B .

Glattheit spielt eine wichtige Rolle bei modernen Faktorisierungsverfahren.

Beispiel
Die Zahl N = 60 ist 5-potenzglatt, die Primzahlen 59 und 61 nicht. Übrigens ist
»(5) = 60.
Die Zahl 2104 · 344 · 549 · 747 ist 7-glatt und 747 -potenzglatt (747 ≈ 5 · 1039 ).

Bemerkung
Eine natürliche Zahl m ∈ N ist genau dann B-potenzglatt, wenn gilt m | »(B) .
196 11 Faktorisierung

11.3.3 Der Algorithmus

Im nachfolgenden Algorithmus wird es deutlich, wie man a»(B) sukzessive aus-
rechnet. Die Eingabe ist die natürliche Zahl N, die es zu faktorisieren gilt. Die
Ausgabe ist ein echter Teiler von N oder Pech gehabt.

W¤hle B ∈ N und bestimme alle Primzahlen p1 , . . . , pn kleiner gleich B, am
Besten beginnend mit p1 = 2 der Größe nach geordnet.
ν
W¤hle νi ∈ N maximal mit pi i ¤ B für alle i ∈ {1, . . . , n}.

W¤hle a0 ∈ N >1 mit ggT(a0 , N) = 1.
ν
pi i
Berechne iterativ ai ≡ (mod N) mit 0 < ai < N für i = 1, . . . , n und
ai’1
bestimme d := ggT(ai ’ 1, N).

Falls d = 1 n¤chstes i.
Falls d > 1 n¤chster Schritt.

Falls d = N, gib d zurück, sonst Pech gehabt.

Falls stets d = 1, d. h. ggT(an ’ 1, N) = 1, dann gibt es keinen B -glatten Prim-
teiler von N “ Pech gehabt.

Im sehr seltenen Fall, dass d = N ist, lohnt es sich evtl. den Algorithmus mit
einem neuen Startwert a0 nochmals zu durchlaufen. Im übrigen bedeutet d = N,
dass es Primteiler p von N gibt, für die p ’ 1 B -potenzglatt ist.

Bemerkung
In MAPLE wurde beispielsweise B = 2000 gew¤hlt. Cohen [7] schl¤gt B zwischen
105 und 106 vor. Die Wahl von B beein¬‚usst stark die Laufzeit, aber auch die
Wahrscheinlichkeit, eine Zerlegung zu ¬nden.

Die p ’ 1 -Methode von Pollard wird manchmal mit einer kleinen Schranke wie
B = 2 000 angewendet, um relativ kleine Primteiler zu ¬nden. Die Methode ist
aber auch von theoretischem Interesse, weil sie

• die Idee liefert für Lenstras Elliptische Kurven Methode (siehe Kapitel 14).

• einen Angriff auf das RSA-Verfahren darstellt. Wie schon in Abschnitt 7.4.1
erw¤hnt, sollte die Primzahlen p und q so gew¤hlt werden, dass p ’ 1 und
q ’ 1 jeweils einen großen Primteiler haben.

eine Verallgemeinerung besitzt zur sogenannten p + 1-Methode, die eben-

falls Auswirkungen auf die Wahl der Primzahlen bei RSA hat. Siehe auch
dazu Abschnitt 7.4.1.
11.4 Faktorisierung mit Differenzen von Quadraten 197

11.4 Faktorisierung mit Differenzen von Quadraten

Die Grundidee geht auf Fermat zurück und wurde bereits im Beweis zu Lem-
ma 9.3 im Zusammenhang mit dem Rabin-Verfahren verallgemeinert. Viele mo-
derne Faktorisierungsverfahren beruhen auf dieser Idee.


11.4.1 Das Verfahren von Fermat

Ist die Zahl N Produkt zweier ungef¤hr gleich großer Faktoren, so kann folgende
Strategie zum Erfolg führen:

Prüfe, ob N ∈ N.

W¤hle w = N.

Prüfe der Reihe nach, ob für i = 1, 2, . . . die Zahl yi = (w + i)2 ’ N eine
Quadratzahl ist.
√ √
Im Erfolgsfall ist N = (w + i ’ yi ) (w + i + yi ) ein Zerlegung von N.

Beispiel
Wir Faktorisieren die Zahl N = 3 240 809 nach der Methode von Fermat. Es ist

N = 1800 und man ¬ndet nach nur drei Schritten

18032 ’ N = 3 250 809 ’ 3 240 809 = 10 000 = 1002 .

Daher gilt N = (1803 ’ 100) (1803 + 100) = 1703 · 1903. Die beiden Faktoren mit
diesem Verfahren weiter zu faktorisieren, ist schon sehr mühsam.


11.4.2 Die gemeinsame Idee der Kettenbruchmethode, des quadratischen
Siebs und weiterer Verfahren

Wir schildern noch einmal die grunds¤tzliche Vorgehensweise aus dem Beweis
von Lemma 9.3. Sie stellt eine Verallgemeinerung des Verfahrens von Fermat dar.

Prüfe, ob N Potenz einer Primzahl ist (vgl. Aufgabe 8.6), falls ja “ Stop!

W¤hle x ∈ Z mit ggT(x, N) = 1 und berechne x2 modulo N.

Suche y ∈ Z mit x2 ≡ y2 (mod N).

Bestimme d := ggT(y ’ x, N).

Falls d ∈ {1, N} neues x, sonst gib d aus “ Stop!
198 11 Faktorisierung

Hat man y gefunden, so folgt aus Aufgabe 11.4, dass dieser Algorithmus mit
Wahrscheinlichkeit ≥ 0.5 abbricht und einen echten Teiler von N liefert.
Das eigentliche Problem ist, die Zahl y zu ¬nden. Um das zu bewerkstelligen, feh-
len uns noch zwei wichtige Schritte, die wir im Anschluss beschreiben. Der erste
Schritt ist allen Verfahren gemeinsam. Erst im zweiten Schritt unterscheiden sich
die verschiedenen Verfahren. Das ist der Schritt, der die Laufzeit entscheidend
beein¬‚usst.


11.4.3 Die Kongruenzen

Um y zu konstruieren, werden Kongruenzen der folgenden Form produziert:
ν
ν
≡ (’1)ν01 p111 · · · pr r1 (mod N) ,
2
x1
ν ν
≡ (’1)ν02 p112 · · · pr r2 (mod N) ,
2
x2
. . .
. . .
. . .
ν
≡ (’1)ν0s p11s ν
· · · pr rs (mod N) ,
x2
s

wobei die pi Primzahlen aus einer sogenannten Faktorbasis sind. Zur Vereinfa-
chung der Schreibweise setzen wir p0 = ’1.
Die Verfahren unterscheiden sich in der Art, wie diese Kongruenzen gewonnen
werden. Gemeinsam ist allen, dass geeignete Zahlen xi quadriert werden, dann
modulo N reduziert (mit Resten zwischen ’N und N) und anschließend die Res-
te “ soweit möglich “ faktorisiert werden. Dabei werden nur die Primzahlen aus
der gegebenen Faktorbasis getestet. Es werden dann (mit evtl. Ausnahmen) nur
die Kongruenzen weiter verwendet, bei denen diese Faktorisierung vollst¤ndig
möglich ist.
Ist es gelungen, genügend viele solcher Kongruenzen zu erzeugen, so kann man
hoffen, dass es μi ∈ {0, 1} gibt mit
⎛ ⎞ ⎛⎞
⎞ μ0 0

ν01 ν02 . . . . . . ν0s ⎜μ ⎟ ⎜0⎟
⎜ν11 ν12 . . . . . . ν1s ⎟ ⎜ . ⎟ ⎜ . ⎟
1
⎜ . ⎟ ⎜.⎟
⎜ ⎟
. ⎟ ⎜ . ⎟ ≡ ⎜ . ⎟ (mod 2)
(—) ⎜.
. ⎠⎜ ⎟ ⎜ ⎟
.
⎝. . ⎜ . ⎟ ⎜.⎟
. . .
⎝ . ⎠ ⎝.⎠.
.
νr1 νr2 . . . . . . νrs
μs 0

und μ j = 0 für mindestens ein j. Das System (—) kann man als lineares Glei-
chungssystem über dem Körper Z2 auffassen. Hat das System mehr Spalten als
Zeilen, so existiert eine nichttriviale Lösung (μ0 , . . . , μs ). Setzt man für eine nicht-
triviale Lösung von (—)
s r 1
‘r νij μ j
μ
∏ ∏ pi

<< . .

. 25
( : 33)



. . >>