Cryptography Reference
In-Depth Information
Das ist die Rekursionsvorsch
ri
ft für die Bestimmung der Koeffizienten
a
i
der Ke
t-
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 si
nd
die Werte U
i
u
nd V
i
aus
(
♣
)
für alle i
∈
N
<
√
N und V
i
<
2
√
N.
natürliche Zahlen, und es gilt U
i
=
Beweis.
Wir beweisen die Behauptung durch Induktion nach
i
. Für
i
1 gilt:
√
N
<
√
N
,
=
∈
Z
<
U
1
und
0
U
1
√
N
2
√
N
1
2
2
√
N
.
U
1
∈
Z
V
1
=
N
−
und
0
<
N
−
<
N
−
−
<
∈
N
Das erledigt den Induktionsanfang. Sind nun für ein
i
die Wert
U
i
,
V
i
und
V
i
−
1
ganzzahlig, so gilt auch
U
i
+
1
∈
Z
. Weiter ist
U
i
+
1
V
i
−
U
i
N
2
N
−
N
−
(
a
i
V
i
−
U
i
)
a
i
V
i
=
=
=
−
+
V
i
+
1
2
a
i
U
i
V
i
V
i
a
i
V
i
=
−
+
∈
Z
V
i
−
1
2
a
i
U
i
.
<
√
N
und
∈
N
die Abschätzungen 0
<
U
i
Wir nehmen nun an, dass für ein
i
V
i
>
0 gelten. Nach Konstruktion ist
√
N
√
N
+
U
i
U
i
+
U
i
+
1
V
i
−
U
i
+
1
(
∗
)
0
<
x
i
−
a
i
=
−
=
<
1,
V
i
V
i
alle irrational sind. Das ergibt zunächst
U
i
+
1
<
√
N
. Wir zeigen nun
weil die
x
i
>
>
(
♣
)
∈
N
≤
<
U
i
+
1
0. Im Fall
V
i
U
i
folgt da
s
direkt aus
, weil
a
i
. Im Fall
V
i
U
i
√
N
erhält man wegen
<
√
N
(
∗
)
0
−
V
i
<
U
i
+
1
.
Das zeigt auch, dass
√
N
+
U
i
+
1
positiv ist. Multipliziert man die Ungleichung
(
∗
)
mit diesem Ausdruck, so ergibt sich in der Mitte die Defin
iti
on von
V
i
+
1
, und
es folgt
V
i
+
1
2
√
N
. Damit sind al
le
+
U
i
U
i
+
1
a
i
>
=
<
0. Schließlich hat man
V
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
a
0
;
a
1
,...
der irrationalen
Zahl
√
N ist
periodisch
. Das bedeutet, es gibt v
,
∈
N
so, dass a
i
+
=
≥
a
i
für alle i
v.
Die minimale Periodenlänge ist kleiner als
2
N.
Wir kommen nun zu der Aussage, die für die Faktorisierung entscheidend ist.
