Cryptography Reference
In-Depth Information
Bemerkung
Es ist überaus bemerkenswert, dass es Probleme
Π
in
NP
gibt, die maximal be-
Π
∈
Π
≺
Π
züglich der Relation „
≺
“ sind, d. h. dass für alle Probleme
NP
gilt
.
Man nennt solche maximalen Probleme
NP -vollständig.
Die Frage nach der Gleichheit der Komplexitätsklassen
P
und
NP
lässt sich so-
mit auf das Studium von
NP
-vollständigen Problemen zurückführen.
Statt der
Zeitkomplexität
, die wir bisher ausschließlich betrachtet haben, kann man
auch die
Speicherkomplexität
betrachten. Es geht hierbei um die Frage, wie viel
Speicherplatz man braucht, um einen Algorithmus durchzuführen. Wir gehen
dieser Problematik nicht weiter nach und unterstellen stets unendliche Speicher-
kapazität. Aber natürlich ist die Frage nach der Speicherkomplexität zumBeispiel
beim Design von Smartcards durchaus relevant.
Ebenfalls wichtig ist die Frage, welche Laufzeit ein Algorithmus im
Durchschnitt
(engl.
avarage case
) hat. Es gibt Beipiele von Algorithmen, die zwar im
schlechtesten
Fall
(engl.
worst case
) exponentiell, aber im Durchschnitt sehr schnell sind.
4.2 Der erweiterte euklidische Algorithmus
Wir halten einige einfache Aussagen zur Teilbarkeit in
fest. Die Aussagen sind
bekannt bzw. leicht zu zeigen, daher verzichten wir auf die Beweise.
Z
4.2.1 Teilbarkeit in den ganzen Zahlen
Wir sagen: Eine ganze Zahl
b
teilt
eine ganze Zahl
a
, in Zeichen
b
|
a
, wenn es ein
∈
Z
=
q
bq
.Inder
Kongruenzschreibweise
(vgl. die Bemerkung auf Seite
62) lautet das wie folgt:
gibt mit
a
b
|
a
⇔
a
≡
0
(
mod
b
)
.
Lemma 4.8
Für ganze Zahlen a
,
b
,
c gilt:
(a) Die Relation
|
ist reflexiv und transitiv, d. h. a
|
a und aus a
|
b und b
|
c folgt a
|
c.
|
|
|
|
=
|
|
(b) Aus a
b und b
a folgt
a
b
.
(c)
0
|
a impliziert a
=
0
, und a
|
0
.
|
|
|
+
∈
Z
(d) Aus b
a und b
c folgt b
ax
c y für alle x
,
y
.
Wir werden diese Aussagen im Folgenden häufig ohne explizites Zitat verwen-
den.
