Cryptography Reference
In-Depth Information
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
.
√
N
.
=
Wähle
w
2
=
=(
+
)
−
Prüfe der Reihe nach, ob für
i
1, 2, . . . die Zahl
y
i
w
i
N
eine
Quadratzahl ist.
−
√
y
i
)(
+
√
y
i
)
=(
+
+
Im Erfolgsfall ist
N
w
i
w
i
ein Zerlegung von
N
.
Beispiel
Wir
F
aktorisieren die Zahl
N
=
3 240 809 nach der Methode von Fermat. Es ist
√
N
=
1800 und man findet nach nur drei Schritten
1803
2
100
2
.
−
N
=
3 250 809
−
3 240 809
=
10 000
=
Daher gilt
N
1903. Die beiden Faktoren mit
diesem Verfahren weiter zu faktorisieren, ist schon sehr mühsam.
=(
1803
−
100
)(
1803
+
100
)=
1703
·
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!
1 und berechne
x
2
modulo
N
.
Wähle
x
∈
Z
mit ggT
(
x
,
N
)=
mit
x
2
y
2
Suche
y
∈
Z
≡
(
mod
N
)
.
=
(
−
)
Bestimme
d
:
ggT
y
x
,
N
.
Falls
d
∈{
1,
N
}
neues
x
, sonst gib
d
aus - Stop!
