Cryptography Reference
In-Depth Information
Bemerkung
Der zu
b
∈
Q
(existierende und eindeutig bestimmte) eigentliche Kettenbruch
kann also mithilfe des euklidischen Algorithmus effizient berech-
net werden. Das wird für den
Wiener-Angriff
auf das RSA-Kryptosystem wichtig
sein.
a
0
;
a
1
,...,
a
n
7.5.3 Ermittlung der Näherungsbrüche
Wir geben nun ein Verfahren an, mit dem wir die Zähler und Nenner der Nähe-
rungsbrüche
[
a
0
;
a
1
,...,
a
k
]
aus der Kettenbruchdarstellung
a
0
;
a
1
,...,
a
n
be-
stimmen können. Dazu benutzen wir die folgende Aussage:
Lemma 7.13
Es seien a
0
∈
Z
∈
N
und a
1
,...,
a
n
gegeben, und p
k
bzw. q
k
seien rekursiv erklärt
durch
p
0
:
=
a
0
;
p
1
:
=
a
1
a
0
+
1;
p
k
:
=
a
k
p
k
−
1
+
p
k
−
2
für k
≥
2;
=
=
=
+
≥
q
0
:
1;
q
1
:
a
1
;
q
k
:
a
k
q
k
−
1
q
k
−
2
für k
2.
=
Dann gilt für alle möglichen k
0, 1, . . .
:
∈
Z
=
≤
<
≥
≥
(a)
p
k
,
q
k
,
1
q
0
q
1
; und q
k
q
k
+
1
, falls k
1
;q
k
k.
k
,
(b)
p
k
+
1
q
k
−
q
k
+
1
p
k
=(
−
1
)
k
a
k
+
2
,
(c)
p
k
+
2
q
k
−
q
k
+
2
p
k
=(
−
1
)
a
k
p
k
−
1
+
p
k
−
2
(d)
Für jedes k
≥
2
gilt
[
a
0
;
a
1
,...,
a
k
]=
q
k
−
2
.
+
a
k
q
k
−
1
p
k
[
]=
(
)=
(e)
a
0
;
a
1
,...,
a
k
q
k
, und
ggT
p
k
,
q
k
1
.
Beweis.
(a) folgt direkt aus den Definitionen.
(b) stimmt für
k
=
−
=(
+
)
·
−
=
0:
p
1
q
0
q
1
p
0
a
1
a
0
1
1
a
1
a
0
1. Wenn die Aussage
für
k
∈
N
0
richtig ist, folgt
p
k
+
2
q
k
+
1
−
q
k
+
2
p
k
+
1
=(
a
k
+
2
p
k
+
1
+
p
k
)
q
k
+
1
−
(
a
k
+
2
q
k
+
1
+
q
k
)
p
k
+
1
k
k
+
1
.
=
p
k
q
k
+
1
−
q
k
p
k
+
1
=
−
(
−
1
)
=(
−
1
)
≥
(c) Für jedes
k
0 gilt
p
k
+
2
q
k
−
q
k
+
2
p
k
=(
a
k
+
2
p
k
+
1
+
p
k
)
q
k
−
(
a
k
+
2
q
k
+
1
+
q
k
)
p
k
k
a
k
+
2
.
=
(
−
)=(
−
)
a
k
+
2
p
k
+
1
q
k
q
k
+
1
p
k
1
(d) Für
k
=
2 gilt
1
a
2
a
0
a
1
+
a
0
+
a
2
a
2
p
1
+
p
0
[
]=
+
a
2
=
=
a
0
;
a
1
,
a
2
a
0
.
1
+
+
a
2
a
1
1
a
2
q
1
q
0
a
1
+
