Cryptography Reference
In-Depth Information
Eine typische Anwendung ist z. B. die Multiplikation zweier Zahlen
a
und
b
mo-
dulo
m
mit Faktoren 0
≤
<
m
: Die Divisionmit Rest wird auf
ab
angewendet,
um den kleinsten positiven Vertreter von
ab
a
,
b
∈
Z
m
zu bestimmen. Man beachte,
dass
a
,
b
und
ab
ungefähr so groß wie
m
sind. Beide Teilschritte des Algorithmus,
nämlich die Multiplikation und die Division mit Rest, sind quadratisch, also kann
man zusammenfassen:
Lemma 4.6
Die Multiplikation modulo m hat die Laufzeit O
2
((
log
m
)
)
, ist also quadratisch.
Mit einem Beweis, der sich nicht wesentlich von dem für ganze Zahlen unter-
scheidet, ergibt sich für die Laufzeit für die Division von Polynomen mit Rest:
Lemma 4.7
Es seien a
,
b Polynome über einem Körper K, und es gelte b
=
0
. Die Division mit Rest,
also die Bestimmung von q
,
r
∈
K
[
X
]
mit a
=
bq
+
r und
deg
r
<
deg
b, hat die
(
)
Laufzeit O
deg
b
deg
q
.
4.1.6 Komplexitätsklassen
Wir sagen: Ein
mathematisches Problem
Π
gehört zur
•
Komplexitätsklasse P
, falls es einen polynomialen Algorithmus zur Lö-
sung dieses Problems gibt, und zur
•
Komplexitätsklasse NP
, falls es einen polynomialen Algorithmus gibt, der
prüfen kann, ob eine erratene Lösung korrekt ist oder nicht.
Das Symbol
NP
steht dabei für
nondeterministic polynomial time
. Gehört ein Pro-
blem zu
P
, so gehört es offensichtlich auch zu
NP
.
Beispiel
Alle bisher in diesem Kapitel untersuchten Probleme, zu denen wir Algorith-
men angegeben haben, gehören zu
P
. Darunter sind Addition und Multipli-
kation von ganzen Zahlen und von Polynomen, Divison mit Rest, Bestimmung
des ggT, usw.
Die Faktorisierung natürlicher Zahlen ist in
NP
, denn ein zu testender Teiler
kann mittels Division mit Rest überprüft werden. Es wird vermutet, ist aber
nicht bekannt, dass die Faktorisierung natürlicher Zahlen
nicht
zu
P
gehört.
Jedes Problem
aus der Komplexitätsklasse
NP
kann durch Ausprobieren aller
Kandidaten für Lösungen gelöst werden. Diese Herangehensweise zur Lösung
des Problems
Π
hat aber im Allgemeinen eine exponentielle Laufzeit. Hat näm-
lich der Eingabewert die Größe
n
, so hat die Menge, die durchsucht werdenmuss,
Π
