Cryptography Reference
In-Depth Information
Satz 4.15
Für die im euklidischen Algorithmus auftretenden Variablen gilt:
log
b
log
≤
(a) n
.
γ
b
a
2
d
|
| ≤
|
| ≤
∈{
}
(b)
x
k
2
d
,
y
k
für alle k
1, . . . ,
n
.
(c) Die Laufzeit des erweiterten euklidischen Algorithmus beträgt O
(
log
a
log
b
)
.
Beweis.
Wir setzen ohne Einschränkung
a
≥
b
>
0 voraus. Dies impliziert, dass
alle
q
k
>
0 sind. Das werden wir mehrfach verwenden.
(a) Unter Nutzung der Beziehung 1
+
γ
−
1
=
γ
zeigen wir zunächst
−
n
k
d
für alle 0
≥
γ
≤
≤
r
k
k
n
=
=
−
mit absteigender Induktion nach
k
. Der Induktionsanfang für
k
n
und
k
n
1
ist einfach:
0
d
und
r
n
−
1
=
≥ γ
≥
> γ
r
n
d
2
d
d
.
Für den Induktionsschluss rechnen wir:
n
−
k
d
n
−
k
−
1
d
r
k
−
1
=
q
k
r
k
+
r
k
+
1
≥
r
k
+
r
k
+
1
≥
γ
+
γ
−
k
1
+
γ
−
1
d
n
n
−
k
+
1
d
.
=
γ
=
γ
log
b
log
n
und somit
n
=
≥ γ
≤
Insbesondere gilt
b
r
0
.
γ
gilt
−
q
k
1
10
∈{
}
=
(b) Für
k
1,...,
n
und die Matrizen
Q
k
:
Q
k
x
k
x
k
+
1
x
k
und
Q
k
y
k
y
k
+
1
y
k
.
=
=
x
k
−
1
y
k
−
1
Mit
x
1
x
0
1
0
und
y
1
y
0
erhält man
−
q
0
1
=
=
Q
1
1
x
n
+
1
x
n
,
Q
n
Q
1
−
y
n
+
1
y
n
.
q
0
1
(
∗
)
···
=
···
=
Q
n
0
Der Knackpunkt des Beweises ist die Untersuchung der Matrizen
u
k
:
u
k
+
1
(
∗∗
)
=
···
Q
n
Q
n
−
1
Q
k
+
1
.
v
k
v
k
+
1
Es gilt
u
k
−
u
k
−
1
u
k
v
k
−
1
.
−
+
u
k
+
1
q
k
1
10
q
k
u
k
u
k
+
1
u
k
=
=
v
k
v
k
+
1
−
q
k
v
k
+
v
k
+
1
v
k
v
k
