Cryptography Reference
In-Depth Information
Satz 11.5
Es sei N
∈
N
(
♣
)
kein Quadrat und die Werte U
i
und V
i
durch die Rekursion
bestimm
t.
aus der Kettenbruchentwicklung von
√
N
P
i
Für Näherungsbrüche
Q
i
=[
a
0
;
a
1
,...,
a
i
]
∈
N
gilt für alle i
die Beziehung
P
i
−
NQ
i
=(
−
i
+
1
V
i
+
1
und daher P
i
≡
(
−
i
+
1
V
i
+
1
)
)
(
)
1
1
mod
N
.
Beweis.
Nach den Lemmata 7.14 und 7.13 (d) (man beachte, dass die dortige Aus-
sage auch für
a
k
∈
R
∈
N
richtig ist) gilt für alle
i
:
√
N
x
i
+
1
P
i
+
P
i
−
1
=[
]=
a
0
;
a
1
,...,
a
i
,
x
i
+
1
.
+
x
i
+
1
Q
i
Q
i
−
1
√
N
+
U
i
+
1
V
i
+
1
Setzt man
x
i
+
1
=
ein, so erhält man
√
N
P
i
+
√
N
+
U
i
+
1
P
i
P
i
−
1
V
i
+
1
=
√
NQ
i
+
+
U
i
+
1
Q
i
Q
i
−
1
V
i
+
1
und
NQ
i
−
√
N
0.
Weil
√
N
irrational ist und alle anderen Größen ganzzahlig sind, geht das nur für
U
i
+
1
P
i
+
P
i
−
1
V
i
+
1
−
(
U
i
+
1
Q
i
+
Q
i
−
1
V
i
+
1
−
P
i
) =
+
−
=
+
−
=
U
i
+
1
P
i
P
i
−
1
V
i
+
1
NQ
i
0
und
U
i
+
1
Q
i
Q
i
−
1
V
i
+
1
P
i
0.
Elimination von
U
i
+
1
aus diesen Gleichungen führt auf
(
P
i
−
NQ
i
−
)
=
P
i
Q
i
−
1
P
i
−
1
Q
i
V
i
+
1
.
Mit Lemma 7.13 (b) folgt die Behauptung.
Beispiel
Wir wählen
N
=
♣
15, führen einige Iterationssc
hri
tte der Rekursion (
) durch und
erhalten so die Kettenbruchdarstellung von
√
15.
i
0
1
2
3
U
i
0
3
3
3
V
i
1
6
1
6
x
i
√
15
√
15
√
15
√
15
+
+
3
3
+
3
6
6
a
i
3
1
6
1
Da die Spalten für
i
3 identisch sind, wiederholt sich die Rekur-
sion bereits ab dieser Stelle, und es ist (mit der für periodische Dezimalbrüche
bekannten Schreibweise)
=
1 und für
i
=
=
3; 1, 6, 1, 6, 1, 6, . . .
3; 1, 6
der unendliche Kettenbruch zu
√
15.
