Cryptography Reference
In-Depth Information
Die Behauptung sei richtig für ein
k
≥
2. Es folgt
1
a
k
+
1
]=
(
+
a
k
+
1
)
+
a
k
p
k
−
1
p
k
−
2
1
[
a
0
;
a
1
,...,
a
k
+
1
]=[
a
0
;
a
1
,...,
a
k
+
1
(
+
a
k
+
1
)
+
a
k
q
k
−
1
q
k
−
2
a
k
+
1
(
a
k
p
k
−
1
+
p
k
−
2
)+
p
k
−
1
a
k
+
1
p
k
+
p
k
−
1
=
q
k
−
1
=
.
(
+
)+
+
a
k
+
1
a
k
q
k
−
1
q
k
−
2
a
k
+
1
q
k
q
k
−
1
Damit ist (d) bewiesen.
(e) Für
k
=
=
0 bzw.
k
1 besagt die erste Behauptung:
a
0
1
=
p
0
q
0
1
a
1
=
a
0
a
1
+
1
p
1
q
1
[
a
0
]=
a
0
=
bzw.
[
a
0
;
a
1
]=
a
0
+
=
.
a
1
a
k
p
k
−
1
+
p
k
−
2
p
k
≥
[
]=
a
k
q
k
−
1
+
q
k
−
2
=
Im Fall
k
q
k
.
Nach der Aussage in (b) existieren zu
p
k
und
q
k
ganze Zahlen
r
,
s
mit
2 erhält man mit (d):
a
0
;
a
1
,...,
a
k
+
=
rq
k
sp
k
1.
Nach Lemma 4.8 (d) folgt hieraus ggT
(
p
k
,
q
k
)=
1.
Die Berechnung der
Näherungszähler
p
k
und
Näherungsnenner
q
k
führt man
zweckmäßigerweise in folgendem Schema durch:
···
a
k
a
0
a
1
a
2
a
3
+
+
+
···
p
k
a
0
a
1
a
0
1
a
2
p
1
p
0
a
3
p
2
p
1
+
+
···
q
k
1
a
1
a
2
q
1
q
0
a
3
q
2
q
1
Beispiel
Wir berechnen die Näherungsbrüche von
2; 1, 2, 3, 1, 2, 1, 3, 4
:
a
k
2123 1 2 1 3 4
p
k
238 7 5 7 2 32104
q
k
113 0 3 6 9 3 1
Damit sind die Näherungsbrüche der Reihe nach
2
1
,
3
1
,
8
3
,
27
10
,
35
13
,
97
36
,
132
49
493
183
,
2104
781
,
.
Der Wert des eigentlichen Kettenbruchs
2; 1, 2, 3, 1, 2, 1, 3, 4
ist
2104
781
=
2.69398... .
Für die Näherungsbrüche gilt
2
1
<
8
3
<
35
13
<
132
49
493
183
.
Diese Abschätzungen werden immer besser. Das ist kein Zufall, wir gehen die-
sem Phänomen im übernächsten Abschnitt nach.
2104
781
3
1
,
2104
781
27
10
,
2104
781
97
36
,
2104
781
<
<
<
<
<
