Cryptography Reference
In-Depth Information
Lemma 4.1 unterscheiden sich nicht sehr. Sind
m
und
n
ungefähr gleich groß,
dann sind beide quadratisch.
Ist aber
n
beschränkt, so ist der
naive
Algorithmus immer noch quadratisch, wäh-
rend das Lemma eine lineare Laufzeit liefert.
Im Folgenden untersuchen wir die Komplexität einiger weiterer für kryptografi-
sche Anwendungen wichtiger Algorithmen.
Wie geschehen unterstellen wir bei allen Betrachtungen, dass gewisse Grund-
operationen in
O
(
)
1
(also in konstanter Zeit) durchgeführt werden können.
4.1.4 Addition und Multiplikation ganzer Zahlen
∈
N
≥
2
die
g
-adische Darstel-
Wir wählen für zwei natürliche Zahlen
a
,
b
und
g
lung
. Das bedeutet:
m
i
=
0
a
i
g
i
und
b
=
n
j
=
0
b
j
g
j
mit 0
≤
a
i
,
b
j
<
g
.
=
a
In der Praxis ist vor allem die
Binärdarstellung
, d. h. der Fall
g
2 wichtig.
Der übliche (schon in der Grundschule gelehrte) Algorithmus zur Addition der
Zahlen
a
und
b
ist gegeben durch:
=
u
0
:
=
0 und
c
:
=
a
+
b
+
u
−
u
·
g
für
∈{
0, . . . , max
{
n
,
m
}
+
1
}
.
+
1
Dabei wird
u
1
so gewählt, dass 0
≤
c
<
g
. In jedem Schritt wird also modulo
+
∈{
}
g
addiert. Man sieht leicht, dass
u
0, 1
. Man nennt
u
+
1
den
Übertrag
an
+
1
der
-ten Stelle. Es gilt dann
{
}
+
max
n
,
m
1
g
.
∑
=
0
a
+
b
=
c
Mit gutem Recht kann man annehmen, dass die Bestimmung von
c
und
u
+
1
in
(
)
jedem Schritt die Laufzeit
O
1
hat. Das ist die
Grundoperation
in diesem Beispiel.
Es folgt:
Lemma 4.2
Die Laufzeit der Addition zweier Zahlen a und b aus
N
beträgt O
(
max
{
log
a
, log
b
}
)
.
Der gezeigte Algorithmus ist also auf jeden Fall linear. Für die Multiplikation
natürlicher Zahlen geht man ganz analog vor. Die Grundoperation hierbei ist die
Multiplikation
modulo
g
mit Übertrag, und man erhält für die Laufzeit:
Lemma 4.3
Die Laufzeit der Multiplikation zweier Zahlen a und b aus
N
beträgt O
(
log
a
log
b
)
.
