Cryptography Reference
In-Depth Information
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 bekomm
e
n, wurde vorgeschlagen, die Ket-
tenbruchentwicklung der irrationalen Zahl
√
N
zu benutzten.
11.5.1 Die Kettenbruchentwicklung von
√
N
Wir erinnern daran, wie die Kettenbruchentwicklung durch eine Rekursionsfor-
mel bestimmt wird (vgl. Abschnitt 7.5.4):
=
√
N
,
1
x
0
:
a
0
:
=
x
0
,
x
i
+
1
:
=
,
a
i
+
1
:
=
x
i
+
1
.
−
x
i
a
i
der unendliche Kettenbruch zu
√
N
und die
x
i
Es ist dann
a
0
;
a
1
,...
sind die
Restwerte
.
Im vorliegenden Spezialfall einer Quadratwurzel erhält man die Koeffizienten
a
0
,
a
1
, . . . der Kettenbruchentwicklung auch durch eine andere Methode. Wir de-
finieren rekursiv die Folgen
(
U
i
)
,
(
V
i
)
,
(
x
i
)
und
(
a
i
)
durch
U
0
:
=
0,
V
0
:
=
1 und
∈
N
0
:
für
i
√
N
U
i
+
1
V
i
N
−
+
U
i
(
♣
)
x
i
:
=
,
a
i
:
=
x
i
,
U
i
+
1
:
=
a
i
V
i
−
U
i
,
V
i
+
1
:
=
.
V
i
Lemma 11.2
Für die Folgen
(
x
i
)
und
(
a
i
)
die aus der Rekursion
(
♣
)
entstehen ist
a
0
;
a
1
,
a
2
,...
die
Kettenbruchentwicklung der irrationalen Zahl
√
N, und für jedes i
∈
N
0
ist x
i
der i-te
Restwert.
=
√
N
, sodass die Startwerte übereinstimmen. Wir rechnen
Beweis.
Es gilt
x
0
√
N
=
(
√
N
U
i
+
1
V
i
+
1
+
+
U
i
+
1
)
V
i
V
i
1
√
N
−
a
i
V
i
+
U
i
V
i
1
=
=
√
N
U
i
+
1
=
=
x
i
+
1
.
U
i
+
1
−
−
x
i
a
i
N
−
