Cryptography Reference
In-Depth Information
7.5.5 Abschätzungen
Aus Lemma 7.13 gewinnen wir wichtige Abschätzungen:
Korollar 7.15
Es sei
ein Kettenbruch mit demWert x, und wir definieren wie in Lemma
7.13 die Zahlen p
k
,q
k
und setzen zudem r
k
a
0
;
a
1
,...,
a
n
p
k
q
k
=
=
:
für k
0, . . . ,
n. Dann gilt:
=
(
−
1
)
k
q
k
q
k
+
1
−
≤
<
(a)
r
k
+
1
r
k
für alle
0
k
n.
1
q
k
|
−
| <
≤
<
(b)
r
k
+
1
r
k
für alle
1
k
n.
r
2
(
k
−
1
)
<
r
2
k
<
r
2
l
+
1
<
≥
+
<
(c)
r
2
l
−
1
für alle k
,
l
1
mit
2
k
,2
l
1
n.
<
<
≥
+
<
(d)
r
2
k
x
r
2
l
+
1
für alle k
,
l
0
mit
2
k
,2
l
1
n.
Beweis.
(a) ergibt sich aus Lemma 7.13 (b) mit Division durch
q
k
q
k
+
1
.
(b) folgt aus (a), weil
q
k
+
1
>
≥
q
k
nach Lemma 7.13 (a) für jedes
k
1.
(c) Aus Lemma 7.13 (c) folgt
a
2
k
q
2
(
k
−
1
)
2
(
k
−
1
)
−
r
2
(
k
−
1
)
=(
−
)
q
2
k
>
0 , d. h.
r
2
(
k
−
1
)
<
r
2
k
1
r
2
k
und
a
2
l
+
1
−
1
2
l
−
=(
−
)
q
2
l
−
1
q
2
l
+
1
<
<
r
2
l
+
1
r
2
l
−
1
1
0 , d. h.
r
2
l
+
1
r
2
l
−
1
.
r
2
l
(
a
)
2
l
q
2
l
q
2
l
+
1
(
−
)
1
≤
≤
<
−
=
>
Im Fall
k
l
folgt
r
2
k
r
2
l
r
2
l
+
1
, weil
r
2
l
+
1
0; und im Fall
k
>
l
analog
r
2
k
+
1
−
r
2
k
>
0, und
r
2
k
+
1
<
r
2
l
+
1
.
(d) folgt aus (c).
7.5.6 Charakterisierung von Näherungsbrüchen
Man kann Näherungsbrüche für rationale Zahlen charakterisieren. Dazu benöti-
gen wir einen Hilfssatz.
Lemma 7.16
Es seien x
∈
Q
\
Z
∈
Z
∈
N
=[
]
und p
,q
gegeben; weiter sei x
a
0
;
a
1
,...,
a
n
mit
p
k
q
k
≥
≥
a
n
2
und n
2
. Mit
sei der k-te Näherungsbruch von x bezeichnet (vgl. Lemma
und
p
q
p
k
<
∈{
−
}
=
7.13). Gilt q
q
k
+
1
für ein k
0,...,
n
2
q
k
, so folgt
|
q
k
x
−
p
k
| < |
qx
−
p
|
.
