Cryptography Reference
In-Depth Information
Daher ist die Darstellung in
(
∗∗
)
wohldefiniert, und es gilt
v
k
−
1
=
−
q
k
v
k
+
v
k
+
1
.
Wir zeigen mit absteigender Induktion nach
k
die Aussage:
r
k
2
d
|
| ≤
∈{
}
(i)
v
k
für alle k
0,...,
n
.
r
n
Für
k
=
n
ist die Behauptung
v
n
=
0
≤
2
d
klar; für
k
=
n
−
1 hat man
v
n
−
1
=
1
≤
r
n
−
1
2
d
>
=
|
r
n
−
1
.
Beim Induktionsschluss gehen wir von
k
nach
k
, denn
r
n
−
1
r
n
d
und
d
−
1 und beachten die Dreiecks-
ungleichung:
+
r
k
r
k
+
1
2
d
q
k
r
k
r
k
+
1
r
k
−
1
2
d
|
| ≤
|
|
+
|
| ≤
2
d
+
=
=
v
k
−
1
q
k
v
k
v
k
+
1
q
k
.
2
d
Damit gilt die Behauptung in (i). Wir zeigen weiter:
(ii)
k
k
+
1
x
k
=(
−
)
,
y
k
=(
−
)
1
|
x
k
|
1
|
y
k
|
,
und
|
x
k
|
und
|
y
k
|
sind monoton wachsend
für alle k
∈{
0,...,
n
}
.
=
=
Für
k
1 stimmen die Behauptungen offenbar. Wir führen den Induk-
tionschritt nur für
x
k
aus (für
y
k
geht man entsprechend vor):
0 und
k
k
k
−
1
=
−
+
=
−
(
−
)
|
|
+(
−
)
|
|
x
k
+
1
q
k
x
k
x
k
−
1
q
k
1
x
k
1
x
k
−
1
+
1
q
k
|
x
k
−
1
|
.
k
=(
−
1
)
x
k
|
+
|
>
−
Nach Induktionsvoraussetzung und wegen
q
k
0 haben die Terme
q
k
x
k
und
x
k
−
1
dasselbe Vorzeichen. Daher gilt:
1
q
k
|
=(
−
+
+
k
k
1
(
−
)
|
|
+
|
)
|
|
1
x
k
x
k
−
1
1
x
k
+
1
,
und die Induktion ist komplett. Außerdem folgt
|
x
k
+
1
| ≥
q
k
|
x
k
| ≥ |
x
k
|
. Damit ist
(ii) gezeigt.
Das Produkt
Q
n
Q
n
−
1
...
Q
1
hat wegen
(
∗∗
)
die Form
,
v
0
=
Q
n
Q
n
−
1
...
Q
1
v
1
(
∗
)
=
also gilt nach
die Gleichung
x
n
v
0
. Nun zeigen (ii) und (i):
b
2
d
.
|
x
k
| ≤ |
x
n
|
=
|
v
0
| ≤
Entsprechend ergibt sich aus
(
∗
)
die Gleichung
y
n
=
−
q
0
v
0
+
v
1
und
+
q
0
r
0
r
1
a
2
d
.
|
| ≤ |
| ≤
=
y
k
y
n
2
d
(c) Die
k
-te Division mit Rest hat nach Lemma 4.5 die Laufzeit
O
(
log
q
k
log
r
k
)
.
Insgesamt ergibt sich die Laufzeit:
n
k
=
0
log
q
k
log
r
k
≤
log
b
log
n
k
=
0
q
k
≤
log
b
log
a
,
