<< . .

. 9
( : 33)



. . >>

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 werden muss,
64 4 Komplexit¤t und Einwegfunktionen

im Allgemeinen O (2n ) Elemente. Es müssen also auch O (2n ) Tests durchgeführt
werden. Da die Tests polynomial sind, ist der naive Algorithmus alles Durchpro-
bieren somit exponentiell.
Übrigens gibt es durchaus Probleme mit exponentiellen Lösungs-Algorithmen,
die nicht in NP liegen.

Bemerkung
Der Begriff mathematisches Problem bleibt vage. Wie beim Begriff des Algorithmus
und der Komplexit¤t würde eine pr¤zisere Fassung den Rahmen dieses Buches
sprengen. Anhand der Beispiele sollte aber ein Grundverst¤ndnis möglich sein.
Um diese Begriffe genauer fassen zu können, müssten wir den Begriff der Turing-
Maschine einführen und diskutieren. Das würde den Rahmen einer Einführung
in die algebraischen Methoden der Kryptologie verlassen. Daher verweisen wir
auf die Literatur.

Wie oben bereits festgehalten, liegt P in NP . Es ist eine offene Frage, ob die bei-
den Klassen evtl. gleich sind, ob es also zu jedem Problem aus NP einen polyno-
mialen Algorithmus zur Lösung gibt. Auf die Beantwortung dieser Frage ist ein
Preis von einer Million US-Dollar ausgesetzt. Es ist eines der Millenium-Probleme1 ,
die vom privaten Clay Mathematics Institute zusammengestellt wurden.


4.1.7 Algorithmische „quivalenz

In der Klasse NP gibt es eine re¬‚exive und transitive Relation ≺. Man schreibt

Π1 ≺ Π2 ,

wenn es einen polynomialen Algorithmus gibt, mit dem man das mathematische
Problem Π1 auf das Problem Π2 zurückführen kann. Genauer: Besitzt man ein
Orakel zur Lösung von Π2 , so kann man Π1 in polynomialer Zeit lösen. Ein Ora-
kel ist dabei eine (¬ktive) Maschine, die auf Anfrage eine Lösung eines gewissen
mathematischen Problems ausgibt. Bei uns ist das Π2 . Die Befragung eines Ora-
kels wird bei der Ermittlung von Laufzeiten vernachl¤ssigt.

Beispiel
Für die Probleme prim(N) „prüfe, ob eine gegebene natürliche Zahl N eine Primzahl
ist“ und Fak(N) „faktorisiere die natürliche Zahl N“ gilt prim(N) ≺ Fak(N), da
man prim auf das Problem der Faktorisierung zurückführen kann. Dass das keine
gute Strategie ist, soll uns hier nicht stören.

Zwei mathematische Probleme Π1 und Π2 mit Π1 ≺ Π2 und Π2 ≺ Π1 nennt
man algorithmisch ¤quivalent. Den Nachweis dafür, dass hierdurch auf NP eine
„quivalenzrelation de¬niert wird, haben wir als Übungsaufgabe formuliert.
1 http://www.claymath.org/millennium/P_vs_NP/
4.2 Der erweiterte euklidische Algorithmus 65

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 zum Beispiel
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 Z fest. Die Aussagen sind
bekannt bzw. leicht zu zeigen, daher verzichten wir auf die Beweise.



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
q ∈ Z gibt mit a = b q. In der Kongruenzschreibweise (vgl. die Bemerkung auf Seite
62) lautet das wie folgt:
b | a ” a ≡ 0 (mod b) .

Lemma 4.8
Für ganze Zahlen a, b, c gilt:

(a) Die Relation | ist re¬‚exiv 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.

(d) Aus b | a und b | c folgt b | a x + c y für alle x, y ∈ Z.

Wir werden diese Aussagen im Folgenden h¤u¬g ohne explizites Zitat verwen-
den.
66 4 Komplexit¤t und Einwegfunktionen

4.2.2 Der erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus bestimmt den größten gemeinsamen
Teiler, in Zeichen ggT, zweier (oder mehrerer) ganzer Zahlen.
Sind a1 , . . . , ak ganze Zahlen, so heißt eine Zahl t ∈ Z gemeinsamer Teiler von
a1 , . . . , ak , wenn t | ai für alle i ∈ {1, . . . , k}. Die natürliche Zahl 1 ist immer
ein gemeinsamer Teiler. Ist eines der ai , etwa a1 , ungleich 0, so gilt |t| ¤ |a1 |.
Daher gibt es in diesem Fall ein größtes t ∈ N, das alle a1 , . . . , ak teilt, genannt
der größte gemeinsame Teiler der ai . Wir schreiben dafür t = ggT(a1 , . . . , ak ).
Falls alle a1 , . . . , ak gleich 0 sind, so setzt man ggT(a1 , . . . , ak ) := 0. Der ggT von
endlich vielen Zahlen liegt stets in N0 .
Lemma 4.9
Für alle a, b, q ∈ Z gilt ggT(a, b) = ggT(a + bq, b).

Beweis. Wir benutzen Lemma 4.8 (d) zweimal:

ggT(a, b) | ggT(a + bq, b) | ggT(a + bq ’ bq, b) = ggT(a, b) .

Nun folgt die Aussage aus dem Teil (b) in Lemma 4.8.
Aus dieser einfachen Beobachtung ergibt sich der erweiterte euklidische Algo-
rithmus zur Berechnung des ggT von zwei ganzen Zahlen a und b. Er bestimmt
außerdem zwei ganze Zahlen x und y mit

a x + b y = ggT(a, b) .
Ohne Einschr¤nkung dürfen wir annehmen, dass a ≥ b > 0 gilt. Wir bestimmen
durch sukzessive Division mit Rest im i-ten Schritt ganze Zahlen ri , qi , xi , yi mit
r0 = b, 0 ¤ ri < ri’1 und:
i Division mit Rest Darstellung wobei
a = q0 b + r1 r1 = ax1 + by1 =1
1 x1
= ’q0
y1
b = q1 r1 + r2 r2 = ax2 + by2 = ’q1 x1
2 x2
= 1 ’ q1 y1
y2
r1 = q2 r2 + r3 r3 = ax3 + by3 = x1 ’ q2 x2
3 x3
= y1 ’ q2 y2
y3
. . .
. . .
. . .
rk’1 = qk rk + rk+1 rk = axk + byk xk = xk’2 ’ qk’1 xk’1
k
yk = yk’2 ’ qk’1 yk’1
. . .
. . .
. . .
rn’2 = qn’1 rn’1 + rn rn = axn + byn xn = xn’2 ’ qn’1 xn’1
n
yn = yn’2 ’ qn’1 yn’1
n+1 rn’1 = qn rn + rn+1 rn+1 = 0 Stop!
4.2 Der erweiterte euklidische Algorithmus 67

Der Algorithmus bricht ab, weil die ri ∈ N0 streng monoton fallen. Wegen Lem-
ma 4.9 gilt in jedem Schritt ggT(rk , rk’1 ) = ggT(rk+1 , rk ). Daher erhalten wir per
Induktion nach k (mit den Bezeichnungen aus obiger Tabelle):

Satz 4.10 (Der euklidische Algorithmus)
Der euklidische Algorithmus bricht nach n + 1 Schritten ab. Sind a, b ganze Zahlen,
b = 0, so ist der Rest rn der ggT von a und b:

rn = ggT(a, b) .

Weiter liefert der Alorithmus ganze Zahlen x := xn und y := yn mit

ggT(a, b) = a x + b y .

Beispiel 4.11
Wir bestimmen mit dem erweiterten euklidischen Algorithmus ganze Zahlen x
und y mit ggT(840, 455) = x · 840 + y · 455:

i Division mit Rest Darstellung wobei
840 = 1 · 455 + 385 r1 = 840 x1 + 455 y1 x1 = 1
1
y1 = ’1
455 = 1 · 385 + 70 r2 = 840 x2 + 455 y2 x2 = ’1 · 1
2
y2 = 1 ’ 1 · (’1)
385 = 5 · 70 + 35 r3 = 840 x3 + 455 y3 x3 = 1 ’ 5 · (’1)
3
y3 = ’1 ’ 5 · 2
70 = 2 · 35 + 0 r4 = 0
4 Stop!

Wir erhalten
ggT(840, 455) = 35 = 6 · 840 + (’11) · 455 .

Eine einfache, aber wichtige Folgerung ist die fast offensichtliche Kennzeichnung
für den ggT.

Lemma 4.12
Für a, b ∈ Z und d ∈ N0 gilt d = ggT(a, b) genau dann, wenn

d | a und d | b, und
(i)

für jedes t ∈ Z mit t | a und t | b gilt t | d.
(ii)

Beweis. ’: (i) gilt nach Voraussetzung.
(ii) Es gelte t | a und t | b, etwa a = a t und b = b t, für ein t ∈ Z. Ist d = ggT(a, b),
so existieren nach dem euklidischen Algorithmus Zahlen x, y ∈ Z mit

d = a x + b y = a t x + b t y = (a x + b y) t ,
68 4 Komplexit¤t und Einwegfunktionen

sodass also t ein Teiler von d ist.
⇐: Nach (i) ist d ein gemeinsamer Teiler von a und b. Wegen (ii) ist jeder gemein-
same Teiler t von a und b ein Teiler von d. Daher gilt t ¤ d.

Es ist also ggT(a, b) auch maximal bezüglich der Relation | und nicht nur bezüg-
lich ¤. Eine weitere wichtige Folgerung ist:

Lemma 4.13
Teilt eine Primzahl p ein Produkt a b ganzer Zahlen a und b, so teilt p bereits einen der
Faktoren a oder b, d. h.:
p | ab ’ p | a oder p | b .

Beweis. Ist p ein Teiler von b, so sind wir fertig. Ist p kein Teiler von b, so gilt
ggT(p, b) = 1, und nach dem Satz 4.10 zum euklidischen Algorithmus existieren
ganze Zahlen x und y mit p x + b y = 1. Es folgt a p x + a b y = a. Nach Voraus-
setzung teilt p beide Summanden der linken Seite. Nach Lemma 4.8 also auch die
rechte Seite a.

Aus dieser Aussage kann man die Eindeutigkeitsaussage des Fundamentalsatzes
der Arithmetik ohne viel Mühe herleiten. Wir haben das als Aufgabe formuliert.

Satz 4.14 (Fundamentalsatz der Arithmetik)
Jede natürliche Zahl N > 1 l¤sst sich “ bis auf die Reihenfolge der Faktoren “ auf ge-
nau eine Art und Weise als ein Produkt von Primzahlpotenzen schreiben, d. h., es gibt
Primzahlen p1 , . . . , pr und natürliche Zahlen ν1 , . . . , νr ∈ N mit:
r
ν
∏ pi i .
N=
i=1

Sortiert man die Primzahlen der Reihe nach, d. h. setzt man p1 < · · · < pr , so
spricht man von der kanonischen Primfaktorzerlegung der natürlichen Zahl
N > 1.


4.2.3 Komplexit¤tsanalyse des euklidische Algorithmus *
Im folgenden Satz benutzen wir die Zahl

1+ 5
≈ 1.618 . . . < 2 ,
γ :=
2
die auch goldener Schnitt genannt wird. Es ist γ eine Nullstelle des Polynoms
x2 ’ x ’ 1, daher gilt
γ = 1 + γ’1 .
Das werden wir im Folgenden benutzen. Wir verwenden die im vorigen Ab-
schnitt eingeführten Bezeichnungen.
4.2 Der erweiterte euklidische Algorithmus 69

Satz 4.15
Für die im euklidischen Algorithmus auftretenden Variablen gilt:
log b
(a) n ¤ .
log γ

(b) |xk | ¤ |yk | ¤ für alle k ∈ {1, . . . , n}.
b a
2d , 2d

(c) Die Laufzeit des erweiterten euklidischen Algorithmus betr¤gt O(log a log b).

Beweis. Wir setzen ohne Einschr¤nkung a ≥ b > 0 voraus. Dies impliziert, dass
alle qk > 0 sind. Das werden wir mehrfach verwenden.
(a) Unter Nutzung der Beziehung 1 + γ’1 = γ zeigen wir zun¤chst

rk ≥ γn’k d für alle 0 ¤ k ¤ n

mit absteigender Induktion nach k. Der Induktionsanfang für k = n und k = n ’ 1
ist einfach:
rn = d ≥ γ0 d und rn’1 ≥ 2 d > γ d .
Für den Induktionsschluss rechnen wir:

rk’1 = qk rk + rk+1 ≥ rk + rk+1 ≥ γn’k d + γn’k’1 d
= γn’k 1 + γ’1 d = γn’k+1 d.

log b
Insbesondere gilt b = r0 ≥ γn und somit n ¤ log γ .
’qk 1
(b) Für k ∈ {1, . . . , n} und die Matrizen Qk := gilt
1 0

xk xk+1 yk yk+1
= =
und .
Qk Qk
xk’1 xk yk’1 yk

’q0
1
x1 y1
= =
Mit erh¤lt man
und
0 1
x0 y0

’q0
1 xn+1 yn+1
(—) Qn · · · Q1 = Q n · · · Q1 =
, .
0 1
xn yn

Der Knackpunkt des Beweises ist die Untersuchung der Matrizen

uk uk+1
(——) := Qn Qn’1 · · · Qk+1 .
vk vk+1

Es gilt
’qk ’qk uk + uk+1
1
uk uk+1 uk uk’1 uk
= = .
’qk vk + vk+1
1 0
vk vk+1 vk vk’1 vk
70 4 Komplexit¤t und Einwegfunktionen

Daher ist die Darstellung in (——) wohlde¬niert, und es gilt vk’1 = ’qk vk + vk+1 .
Wir zeigen mit absteigender Induktion nach k die Aussage:
r
(i) |vk | ¤ k für alle k ∈ {0, . . . , n}.
2d
Für k = n ist die Behauptung vn = 0 ¤ 2d klar; für k = n ’ 1 hat man vn’1 = 1 ¤
rn
rn’1
2d , denn rn’1 > rn = d und d | rn’1 .
Beim Induktionsschluss gehen wir von k nach k ’ 1 und beachten die Dreiecks-
ungleichung:
q r + rk+1
rk r r
+ k+1 = k k = k’1 .
|vk’1 | ¤ qk |vk | + |vk+1 | ¤ qk
2d 2d 2d 2d
Damit gilt die Behauptung in (i). Wir zeigen weiter:
(ii) xk = (’1)k |xk |, yk = (’1)k+1 |yk |, und |xk | und |yk | sind monoton wachsend
für alle k ∈ {0, . . . , n}.
Für k = 0 und k = 1 stimmen die Behauptungen offenbar. Wir führen den Induk-
tionschritt nur für xk aus (für yk geht man entsprechend vor):

xk+1 = ’qk xk + xk’1 = ’qk (’1)k |xk | + (’1)k’1 |xk’1 |
= (’1)k+1 qk |xk | + |xk’1 | .

Nach Induktionsvoraussetzung und wegen qk > 0 haben die Terme ’qk xk und
xk’1 dasselbe Vorzeichen. Daher gilt:

(’1)k+1 qk |xk | + |xk’1 | = (’1)k+1 |xk+1 | ,

und die Induktion ist komplett. Außerdem folgt |xk+1 | ≥ qk |xk | ≥ |xk |. Damit ist
(ii) gezeigt.
Das Produkt Qn Qn’1 . . . Q1 hat wegen (——) die Form

Qn Qn’1 . . . Q1 = ,
v0 v1

also gilt nach (—) die Gleichung xn = v0 . Nun zeigen (ii) und (i):

b
|xk | ¤ |xn | = |v0 | ¤ .
2d
Entsprechend ergibt sich aus (—) die Gleichung yn = ’q0 v0 + v1 und
q0 r0 + r1 a
|yk | ¤ |yn | ¤ = .
2d 2d
(c) Die k-te Division mit Rest hat nach Lemma 4.5 die Laufzeit O(log qk log rk ).
Insgesamt ergibt sich die Laufzeit:
n n
‘ log qk log rk ¤ log b log ∏ qk ¤ log b log a ,
k=0 k=0
4.3 Die primen Restklassengruppen 71

denn
a ≥ q0 r0 + r1 ≥ q0 (q1 r1 + r2 ) ≥ · · · ≥ qn qn’1 . . . q0 .
Um die Laufzeit für die Berechnung der xk abzusch¤tzen, rechnen wir
n’1 n’1
‘ log qk log xk ¤ log b log ∏ qk ¤ log b log b .
k=1 k=1

Analog ergibt sich für die yk
n’1 n’1
‘ log qk log yk ¤ log a log ∏ qk ¤ log a log b .
k=1 k=1

<< . .

. 9
( : 33)



. . >>