Cryptography Reference
In-Depth Information
denn
≥
+
≥
(
+
)
≥···≥
q
n
q
n
−
1
...
q
0
.
Um die Laufzeit für die Berechnung der
x
k
abzuschätzen, rechnen wir
a
q
0
r
0
r
1
q
0
q
1
r
1
r
2
n
k
=
1
log
q
k
log
x
k
≤
log
b
log
n
−
1
−
1
k
=
1
q
k
≤
log
b
log
b
.
Analog ergibt sich für die
y
k
n
k
=
1
log
q
k
log
y
k
≤
log
a
log
n
−
1
−
1
k
=
1
q
k
≤
log
a
log
b
.
(
)
Da alle Teilaufgaben in
O
log
a
log
b
Schritten erledigt werden können, folgt d
ie
Behauptung.
Bemerkung
Es ist von größter Bedeutung, dass der euklidische Algorithmus ohne eine Fak-
torisierung von
a
und
b
auskommt. Er ist sehr effizient (nicht nur asymptotisch)
und spielt eine fundamentale Rolle in der Zahlentheorie und der Kryptologie.
Der Beweis zeigt auch, dass die Werte für
x
und
y
(und alle Zwischenergeb-
nisse) beschränkt sind. Das impliziert polynomiale Speicherkomplexität. Diese
Aussage gilt nicht nur asymptotisch und trägt zur praktischen Effizienz bei.
Es gibt einen analogen Algorithmus für Polynome, mit ähnlicher Komplexität
(vgl. auch Lemma 4.7).
4.3 Die primen Restklassengruppen
>
In diesem Abschnitt sei eine natürliche Zahl
n
1 fest gewählt.
4.3.1 Einheiten in
Z
n
Die Einheitengruppe des Restklassenringes
(
Z
n
,
+
,
·
)
, das ist die multiplikative
(
Z
n
,
·
)
Gruppe
mit
a
1
,
Z
n
=
{
a
∈
Z
n
;
a
ist invertierbar
}
=
∈
Z
n
;
∃
b
∈
Z
n
mit
a b
=
wird auch
prime Restklassengruppe
modulo
n
genannt.
Satz 4.16
Für a
∈
Z
n
⇔
∈
Z
(
)=
gilt: a
ggT
a
,
n
1
.
=
+
∈
Z
Beweis.
Es sei
a
a
n
Z
invertierbar. Folglich existiert ein
b
mit
1
+
n
Z
=(
a
+
n
Z
)
·
(
b
+
n
Z
)=
ab
+
n
Z
.
