Cryptography Reference
In-Depth Information
Bemerkung
Moderne Faktorisierungs-Algorithmen für natürliche Zahlen haben Laufzeiten
der Form
e
c
√
log
N
log log
N
(
)
>
0.
Das ist zwar nicht polynomial, aber besser als exponentiell. Man nennt sie des-
halb
subexponentiell
.
O
,
c
4.1.3 Multiplikation von Polynomen
Wir betrachten als erstes Beispiel die Laufzeit für die Multiplikation von Poly-
nomen
f
,
g
mit beschränkten Koeffizienten. Das soll bedeuten, dass die
Asymptotik nur von
m
∈
Z
[
X
]
=
=
deg
f
und
n
deg
g
abhängt. Das ist insbesondere für
Z
Polynome über den Restklassenringen
erfüllt. Hier liegen alle Koeffizienten
zwischen 0 und
reduziert werden.
Die Formel auf Seite 35 zeigt, dass man zur Berechnung des
i
-ten Koeffizienten
(
−
1, weil sie in jedem Schritt modulo
1 Multiplikationen von Koeffizienten durchführen muss.
Die Multiplikation der Koeffizienten kann als Grundoperation gewählt werden,
weil die Koeffizienten unabhängig von
m
und
n
beschränkt sind. Da die Kosten
für die Addition wesentlich geringer sind, wird diese hier vernachlässigt. Man
beachte auch, dass die Anzahl der Additionen ungefähr so groß wie diejenige
der Multiplikationen ist, sodass sich eine Berücksichtigung asymptotisch nicht
auswirken würde. Diese Überlegungen führen auf eine erste Abschätzung für
die Laufzeit:
fg
)
i
von
fg
genau
i
+
O
2
.
+
n
m
i
=
0
(
i
+
1
)=
(
m
+
n
+
1
)(
m
+
n
+
2
)
=
(
m
+
n
)
2
≥
Es geht aber besser: Wir nehmen ohne Einschränkung
m
n
an, dann sind für
i
0. Lässt man diese Produkte unberücksich-
tigt, so ergibt sich für die Gesamtzahl aller Multiplikationen:
>
n
gewisse Produkte zwingend
=
(
m
+
1
)(
n
+
1
)=
O
(
mn
)
.
Dabei wird einfach jeder Koeffizient von
f
mit jedem von
g
kombiniert. Dieselben
Überlegungen greifen auch bei Polynomen über endlichen Ringen, wenn man
wieder die Ringmultiplikation als Grundoperation wählt. Wir halten fest:
Lemma 4.1
Sind f und g Polynome über einem endlichen Ring oder über
mit beschränkten
Koeffizienten, so beträgt die Laufzeit der Multiplikation dieser Polynome asymptotisch
O
Z
(
·
)
deg
f
deg
g
.
Bemerkung
Die Laufzeit des zuerst betrachteten
naiven
Algorithmus und die Aussage von
