Cryptography Reference
In-Depth Information
und damit
q
k
−
q
k
+
1
2
1
≤
=
=
0, d. h.
q
k
q
k
+
1
, also gelten
k
0 (vgl. Lemma 7.13
(a)) und Gleichheit anstelle von
≥
in obigen Ungleichungen:
p
0
1
2
q
0
=
1
2
=[
x
=
q
0
+
a
0
+
a
0
;2
]
,
imWiderspruch zur Annahme
q
1
≥
p
1
q
1
p
1
1
2
q
1
sodass
x
=
x
−
.
(b) Es gelte
q
<
p
1
x
−
2
q
2
, und es sei
x
=
a
0
;
a
1
,...,
a
n
ein eigentlicher Ket-
tenbruch mit Wert
x
. Es bezeichnen
p
k
und
q
k
für
k
=
0,...,
n
die in Lemma 7.13
definierten Größen.
1. Fall: q
≥
q
n
. Hier folgt
=
≤
1
qq
n
|
p
n
p
q
p
q
1
2
q
2
,
−
|
=
q
n
−
−
p
n
q
pq
n
x
0, folglich
p
q
p
n
q
n
.
−
=
=
also
p
n
q
pq
n
∈
N
0
mit
q
k
≤
<
2. Fall:
Es gibt ein
k
q
q
k
+
1
.
p
q
p
k
Es sei
=
q
k
angenommen. Mit Lemma 7.16 folgt
1
2
q
,
|
−
| < |
−
| <
q
k
x
p
k
qx
p
sodass
≤
+
<
qq
k
≤
|
−
|
1
p
k
q
pq
k
p
k
p
q
p
k
q
k
p
q
1
2
qq
k
+
1
2
q
2
=
q
k
−
x
−
x
−
qq
k
p
q
p
k
1
q
k
1
q
<
≤
=
und damit
imWiderspruch zu
q
k
q
. Somit gilt
q
k
.
Beispiel
Wir betrachten die Näherungsbrüche für
6
13
=
4.76923.... Es gilt (vgl. das Beispiel
auf Seite 129):
62
13
=[
]
4; 1, 3, 3
.
Wir erhalten die Näherungsbrüche
4
1
,
1
1
=
5
1
,
1
17
4
62
13
[
]=
[
]=
+
[
]=
+
1/3
=
[
]=
4
4; 1
4
4; 1, 3
4
,
4; 1, 3, 3
+
1
und stellen nun fest:
>
<
>
62
13
−
4
1
1
62
13
−
5
1
1
62
13
−
17
4
1
1
2
,
1
2
,
4
2
.
·
·
·
2
2
2
