<< . .

. 26
( : 33)



. . >>

j=1
2
xi i
x := und y := ,
i=1 i=0
11.4 Faktorisierung mit Differenzen von Quadraten 199

so gilt x2 ≡ y2 (mod N), wie gewünscht. Dabei stellt die Wahl der μ j sicher, dass
‘r νij μ j für alle i gerade ist, also y ∈ N gilt.
j=1

Beispiel
Wir erzeugen ad hoc einige Kongruenzen für den Modul N = 91 über der Fak-
torbasis F = {’1, 2, 3, 5}:


≡ ’1 · 2 · 3 · 11 (mod 91)
52
≡ ’1 · 5 · 11 (mod 91)
62
≡ ’1 · 33 (mod 91)
82
≡ ’1 · 2 · 5 (mod 91)
92
≡ 2 · 3 · 5 (mod 91)
112
≡ ’1 · 2 · 19 (mod 91) .
122

Die ersten beiden und die letzte Kongruenz sind zu verwerfen. Das Gleichungs-
system aus der dritten bis fünften Kongruenz lautet
⎛ ⎞
0 ⎛ ⎞ ⎛⎞
1 1
μ 0
⎜0 1⎟ ⎝ 0 ⎠ ⎝ ⎠
1
⎜ ⎟ μ1 ≡ 0 (mod 2)
⎝3 1⎠
0
μ2 0
0 1 1

und hat als Lösung (1, 1, 1)T . Das führt auf

x = 8 · 9 · 11 = 792 , y = (’1) · 2 · 32 · 5 = ’90 und x2 ≡ y2 (mod 91) .

In der Tat gilt ggT(x + y, 91) = ggT(702, 91) = 13.

Bemerkung
Zum Lösen des linearen Gleichungssystems über Z2 bietet sich zun¤chst der
Gauß-Algorithmus an. Wenn die Parameter r, s sehr groß sind, geht das nicht
mehr. Andererseits enth¤lt die Koef¬zientenmatrix sehr viele Nullen, sodass spe-
zialisierte Verfahren erfolgversprechend sind.


11.4.4 Die Faktorbasis

In den beiden Verfahren, die wir behandeln werden, sind diejenigen Primzahlen
p2 , . . . , pr unterhalb einer gewissen Schranke B, für die N ein Quadrat modulo p
ist, zu bestimmen. Dazu kommen p0 = ’1 und p1 = 2. Diese Zahlen fassen wir
zur Faktorbasis zusammen:

F := {’1, 2 , p2 , . . . , pr } , wobei N ein Quadrat modulo pi , pi < B, für i > 1.
200 11 Faktorisierung

Die Bedingung N ist Quadrat modulo pi ist speziell für die zu betrachtenden Ver-
fahren. Sie ist im Allgemeinen durch eine andere, oder gar keine Bedingung zu
ersetzen. Die Absch¤tzung pi ¤ B ist allen Faktorbasen gemeinsam.
Das folgende Lemma gibt Auskunft, wie man die pi für unseren Fall bestimmen
kann.

Lemma 11.1
Es sei p = 2 eine Primzahl. Das Element N ∈ Z — ist genau dann ein Quadrat, wenn
p
p’1
≡ 1 (mod p).
N 2



Beweis. Ist N = a2 ein Quadrat, so folgt die angegebene Kongruenz direkt aus
dem Satz 6.9 (a) von Euler, wenn man a2 für N einsetzt.
Nach dem Satz von Euler sind alle Elemente aus Z — Nullstellen des Polynoms
p
p’1 p’1
’1 + 1 = X p’1 ’ 1 .
X X
2 2


Davon gibt es insgesamt p ’ 1. Nach Korollar 9.2 sind die H¤lfte dieser Elemen-
p’1
te Quadrate. Weil die Quadrate alle Nullstellen von X 2 ’ 1 sind, und dieses
p’1
Polynom nicht mehr als 2 Nullstellen haben kann, müssen die Nichtquadrate
p’1
+ 1 sein. Das zeigt die Behauptung.
Nullstellen des Polynoms X 2



Bemerkung
Mit dem Legendre-Symbol und dem quadratischen Reziprozit¤tsgesetz kann man
ebenfalls entscheiden, ob N ein Quadrat in Z — ist oder nicht.
p

Bei der Erzeugung der Kongruenzen müssen gewisse Zahlen über der Faktorba-
sis in Primfaktoren zerlegt werden, wobei in manchen Verfahren nur Potenzen
pν von Primzahlen p ∈ F mit pν ¤ B akzeptiert werden. Diese Zerlegung gelingt
genau für B-glatte bzw. B-potenzglatte Zahlen. Nun kann es passieren, dass die
Zerlegung nur fast gelingt. Das soll bedeuten, dass nur ein zu großer Primteiler q
übrig bleibt. Eine solche Kongruenz hat die Form
ν
ν
x1 ≡ (’1)ν01 p111 · · · pr r1 · q (mod N) .
2


Natürlich nützt das so nichts, aber wenn eine zweite solche Kongruenz
ν ν
x2 ≡ (’1)ν02 p112 · · · pr r2 · q (mod N) .
2


gefunden wird, kann man die beiden Kongruenzen zu einer brauchbaren Kon-
gruenz kombinieren:

(x1 x2 q’1 )2 ≡ (’1)ν01 +ν02 p111 +ν12 · · · pr r1 +νr2 (mod N) ,
ν
ν


wobei q’1 modulo N zu bestimmen ist.
Wenn solche Primzahlen im Zerlegungsalgorithmus berücksichtigt werden, so
spricht man von der Large Prime Variation.
11.5 Die Kettenbruchmethode von Morrison-Brillhardt * 201

Bemerkung
Statt die beiden Kongruenzen mit dem großen Primteiler zu einer Kongruenz
zu kombinieren, kann man auch die Faktorbasis erweitern bzw. das lineare Glei-
chungssystem um entsprechende Zeilen erg¤nzen.

Wieder zeigt das Geburtstagsparadoxon (siehe Aufgabe 2.2), dass es gar nicht
so abwegig ist, die Large Prime Variation durchzuführen. Das Auftreten von zwei
solchen Kongruenzen mit demselben großen Primteiler ist keineswegs unwahr-
scheinlich (vgl. auch das Beispiel auf Seite 199).


11.5 Die Kettenbruchmethode von Morrison-Brillhardt *

Nach wie vor sei N eine zusammengesetzte natürliche Zahl. Wir dürfen ohne
Einschr¤nkung voraussetzen, dass N nicht Potenz einer Primzahl ist. Um Kon-
gruenzen wie im Abschnitt 11.4.3 zu bekommen, wurde vorgeschlagen, die Ket-

tenbruchentwicklung der irrationalen Zahl N zu benutzten.


N
11.5.1 Die Kettenbruchentwicklung von

Wir erinnern daran, wie die Kettenbruchentwicklung durch eine Rekursionsfor-
mel bestimmt wird (vgl. Abschnitt 7.5.4):
√ 1
x0 := N, a0 := x0 , xi+1 := , ai+1 := xi+1 .
xi ’ ai

Es ist dann a0 ; a1 , . . . der unendliche Kettenbruch zu N und die xi sind die
Restwerte.
Im vorliegenden Spezialfall einer Quadratwurzel erh¤lt man die Koef¬zienten
a0 , a1 , . . . der Kettenbruchentwicklung auch durch eine andere Methode. Wir de-
¬nieren rekursiv die Folgen (Ui ), (Vi ), (xi ) und (ai ) durch U0 := 0, V0 := 1 und
für i ∈ N0 :

N ’ Ui+1
2
N + Ui
(™) xi := , ai := xi , Ui+1 := ai Vi ’ Ui , Vi+1 := .
Vi Vi
Lemma 11.2
Für die Folgen (xi ) und (ai ) die aus der Rekursion (™) entstehen ist a0 ; a1 , a2 , . . . die

Kettenbruchentwicklung der irrationalen Zahl N, und für jedes i ∈ N0 ist xi der i-te
Restwert.

Beweis. Es gilt x0 = N, sodass die Startwerte übereinstimmen. Wir rechnen
√ √
N + Ui+1 ( N + Ui+1 ) Vi 1 1
Vi
=√
xi+1 = = =√ = .
xi ’ ai
N ’ Ui+1 N ’ Ui+1
2 N’ai Vi +Ui
Vi+1
Vi
202 11 Faktorisierung

Das ist die Rekursionsvorschrift für die Bestimmung der Koef¬zienten ai der Ket-

tenbruchentwicklung von N.
Die Rekursion (™) bietet einen vorteilhaften Weg, die Kettenbruchdarstellung zu
bestimmen, weil bei den Rechnungen fast nur kleine ganze Zahlen vorkommen.

Satz 11.3
Es sei N ∈ N kein Quadrat. Dann√ sind die Werte Ui und Vi aus (™) für alle i ∈ N

natürliche Zahlen, und es gilt Ui < N und Vi < 2 N.

Beweis. Wir beweisen die Behauptung durch Induktion nach i. Für i = 1 gilt:
√ √
U1 = N ∈Z und 0 < U1 < N,
√ √ √
2 2
V1 = N ’ U1 ∈ Z und 0 < N ’ < N’ N’1 < 2 N.
2
N

Das erledigt den Induktionsanfang. Sind nun für ein i ∈ N die Wert Ui , Vi und
Vi’1 ganzzahlig, so gilt auch Ui+1 ∈ Z. Weiter ist

N ’ Ui+1 N ’ Ui2
2
N ’ (ai Vi ’ Ui )2
= = = ’ a2 Vi + 2ai Ui
Vi+1 i
Vi Vi Vi
= Vi’1 ’ a2 Vi + 2ai Ui ∈ Z .
i

Wir nehmen nun an, dass für ein i ∈ N die Absch¤tzungen 0 < Ui < N und
Vi > 0 gelten. Nach Konstruktion ist
√ √
N + Ui Ui + Ui+1 N ’ Ui+1
(—) 0 < xi ’ ai = ’ = < 1,
Vi Vi Vi

weil die xi alle irrational sind. Das ergibt zun¤chst Ui+1 < N. Wir zeigen nun
Ui+1 > 0. Im Fall Vi > Ui folgt das direkt aus (™), weil ai ∈ N. Im Fall Vi ¤ Ui <
√ √
N erh¤lt man wegen (—) 0 < N ’ Vi < Ui+1 .

Das zeigt auch, dass N + Ui+1 positiv ist. Multipliziert man die Ungleichung
(—) mit diesem Ausdruck, so ergibt sich in der Mitte die De¬nition von Vi+1 , und

U +U
es folgt Vi+1 > 0. Schließlich hat man Vi = i a i+1 < 2 N. Damit sind alle
i
Behauptungen bewiesen.
Aus Lemma 11.2 und Satz 11.3 ergibt sich eine einfache Folgerung, die wir als
Übungsaufgabe 11.5 stellen.

Korollar 11.4
Es sei N ∈ N kein Quadrat. Die Kettenbruchentwicklung a0 ; a1 , . . . der irrationalen

Zahl N ist periodisch. Das bedeutet, es gibt v, ∈ N so, dass ai+ = ai für alle i ≥ v.
Die minimale Periodenl¤nge ist kleiner als 2N.

Wir kommen nun zu der Aussage, die für die Faktorisierung entscheidend ist.
11.5 Die Kettenbruchmethode von Morrison-Brillhardt * 203

Satz 11.5
Es sei N ∈ N kein Quadrat und die Werte Ui und Vi durch die Rekursion (™) bestimmt.

P
Für N¤herungsbrüche Qi = [a0 ; a1 , . . . , ai ] aus der Kettenbruchentwicklung von N
i
gilt für alle i ∈ N die Beziehung
Pi2 ’ N Q2 = (’1)i+1 Vi+1 Pi2 ≡ (’1)i+1 Vi+1 (mod N) .
und daher
i

Beweis. Nach den Lemmata 7.14 und 7.13 (d) (man beachte, dass die dortige Aus-
sage auch für ak ∈ R richtig ist) gilt für alle i ∈ N:
√ x P + Pi’1
N = [a0 ; a1 , . . . , ai , xi+1 ] = i+1 i .
xi+1 Qi + Qi’1

N+Ui+1
Setzt man xi+1 = ein, so erh¤lt man
Vi+1

√ N Pi + Ui+1 Pi + Pi’1 Vi+1
N=√
N Qi + Ui+1 Qi + Qi’1 Vi+1
und

Ui+1 Pi + Pi’1 Vi+1 ’ N Qi ’ N (Ui+1 Qi + Qi’1 Vi+1 ’ Pi ) = 0 .

Weil N irrational ist und alle anderen Größen ganzzahlig sind, geht das nur für
Ui+1 Pi + Pi’1 Vi+1 ’ N Qi = 0 und Ui+1 Qi + Qi’1 Vi+1 ’ Pi = 0 .
Elimination von Ui+1 aus diesen Gleichungen führt auf
(Pi Qi’1 ’ Pi’1 Qi ) Vi+1 = Pi2 ’ N Q2 .
i

Mit Lemma 7.13 (b) folgt die Behauptung.

Beispiel
Wir w¤hlen N = 15, führen einige Iterationsschritte der Rekursion (™) durch und

erhalten so die Kettenbruchdarstellung von 15.

0 1 2 3
i
0 3 3 3
Ui
1 6 1 6
Vi
√ √
√ √
15 + 3
15+3 15+3
15
xi 6 6
3 1 6 1
ai
Da die Spalten für i = 1 und für i = 3 identisch sind, wiederholt sich die Rekur-
sion bereits ab dieser Stelle, und es ist (mit der für periodische Dezimalbrüche
bekannten Schreibweise)
3; 1, 6, 1, 6, 1, 6, . . . = 3; 1, 6

der unendliche Kettenbruch zu 15.
204 11 Faktorisierung

11.5.2 Der Algorithmus

Wir schildern nun den Algorithmus von Morrison-Brillhardt. Die Kongruenz aus
Satz 11.5 zeigt, dass N modulo jeden Primteilers von Vk ein Quadrat ist. Daher
werden nur solche Primzahlen in die Faktorbasis F = {p0 , . . . , pr } aufgenom-
men, wie im vorigen Abschnitt 11.4.4 beschrieben. √
Satz 11.5 zeigt, dass für alle k ∈ N die ganze Zahl Vk klein ist: Vk < 2 N. W¤hlt
man die Schranke B geeignet, so darf man hoffen, dass viele der Vk ganz in Prim-
faktoren aus der Faktorbasis F zerfallen, um die gewünschten Kongruenzen zu
erhalten. Anders ausgedrückt: Viele der Vk sind B-glatt.
Für die Rechnung brauchen wir nur die Z¤hler Pk der N¤herungsbrüche, und
diese auch nur modulo N.
Bestimme die Schranke B und die zugehörige Faktorbasis F;
Berechne die Folgen (Uk ), (Vk ), (xk ), (ak ) schrittweise mit der Rekursion (™).
Berechne iterativ Pk ≡ ak Pk’1 + Pk’2 (mod N), 0 ¤ Pk < N, mit den Startwer-
ten P’2 = 0, P’1 = 1.
Setze ν0k ≡ k (mod 2) und Vk := Vk .
˜

Für alle Primzahlen pi aus der Faktorbasis bestimme die höchste Potenz j mit
˜
j
Vk ≡ 0 (mod p ); falls j > 0 ersetze Vk durch Vk und setze νik := j.
˜ ˜ j
i pi

Jedes k, für das am Ende Vk = 1 gilt, liefert eine Kongruenz gem¤ß Ab-
˜
schnitt 11.4.3.
ν ν
Pk ≡ (’1)ν0k p11k · · · pr rk (mod N) .
2

˜
Evtl. liefert die Large Prime Variation noch weitere Kongruenzen, wenn Vk eine
Primzahl ist.
Da der Kettenbruch nach Korollar 11.4 periodisch ist, kann es passieren, dass die
Periode zu klein ist, sodass man zu wenige Kongruenzen ¬ndet. Man w¤hlt
√ √
dann statt N eine Zahl m N mit einem kleinen quadratfreien Multiplikator m
und versucht es erneut.

Bemerkung
Die asymptotische Laufzeit des vorgestellten Algorithmus betr¤gt

2 log N · log log N) .
O exp(

Er war damit der erste subexponentielle Algorithmus zur Faktorisierung.


11.6 Das quadratische Sieb

Wir schildern wie beim quadratischen Sieb die Kongruenzen konstruiert werden.
11.6 Das quadratische Sieb 205

11.6.1 Das Polynom

In der einfachsten Form w¤hlt man das quadratische Polynom
√ 2
f (X) = X + ’N
N

und versucht f (a) für a ∈ Z über der Faktorbasis F ganz in Primfaktoren zu
zerlegen. Gelingt das, so gilt
√ 2 ν (a) ν (a)
≡ (’1)ν0 (a) p11
a+ · · · · · pr r (mod N) .
N

Das ist eine Kongruenz der Form, wie sie in Abschnitt 11.4.3 beschrieben wurde.
Das Polynom ist so gew¤hlt, dass die Werte f (a) relativ klein sind, und so eine
gute Chance haben, über der Faktorbasis F zu zerfallen.

Bemerkung
Beim Multiple Polynomial Quadratic Sieve (MPQS) werden mehrere Polynome der
Form g(X) = a X 2 + 2 b X + c mit a > 0, b2 ’ a c > 0 und N | b2 ’ a c benutzt.
Es gilt dann a g(X) ≡ (aX + b)2 (mod N) und man kann Kongruenzen wie oben
¬nden. Das oben benutzte Polynom f ist ein Spezialfall davon.

Der eigentliche Trick besteht darin, nicht jeden Wert durch alle Primzahlen der
Faktorbasis zu teilen, wie es im vorher beschriebenen Verfahren der Fall war,
sondern nur diejenigen, die wirklich teilbar sind. Dazu dient das Sieb.


11.6.2 Das Sieb

<< . .

. 26
( : 33)



. . >>