<< . .

. 21
( : 33)



. . >>


X r ’ 1 = gs h mit einem h ∈ K[X] .

Wir leiten die Polynome nach X ab und erhalten mit der Produktregel für die
Ableitung:
r X r’1 = s gs’1 g h + gs h .

W¤re s > 1, so h¤tten wir in g einen gemeinsamen Teiler von X r ’ 1 und seiner
Ableitung rX r’1 gefunden. Ein solcher gemeinsamer Teiler w¤re aber auch ein
Teiler der Differenz ’1 dieser Polynome. Folglich muss s = 1 gelten: Jeder Teiler
g von X r ’ 1 mit deg g > 0 kommt in einfacher Potenz vor, d. h. X r ’ 1 = h1 · · · ht
mit verschiedenen irreduziblen Polynomen h1 , . . . , ht .
Für jedes dieser hi gilt hi | f , wie mehrfaches Anwenden von Lemma 3.7 zeigt.
Induktiv folgt f = h1 . . . ht f t = (X r ’ 1) f t für ein Polynom f t ∈ K[X], wie be-
hauptet.

Nun haben wir alle Zutaten, um das folgende Ergebnis über introspektiven Zah-
len begründen zu können. Wir werden es benötigen, um die Korrektheit des AKS-
Algorithmus zu zeigen.

Lemma 8.16
Es sei k ∈ N, und p sei ein Primteiler der natürlichen Zahl n. Falls für jedes a ∈
{0, 1, . . . , k} die Kongruenz

(X + a)n ≡ X n + a (mod (n, X r ’ 1))

gilt, so sind alle Elemente der Menge

t
n
; s, t ∈ N0
s
J := p
p

k
introspektiv für jedes Polynom f ∈ Q := ∏ (X + a)ea ; ea ∈ N0 ⊆ Z p [X] und
a=0
r ∈ N.
160 8 Primzahltests

Beweis. Wir zeigen, dass p und n introspektiv für jedes X + a ∈ Z p [X] und r ∈ N
p
sind. Da nach Lemma 8.14 (a) beliebige Produkte introspektiver Zahlen wieder
introspektiv sind, folgt hieraus die Behauptung für jedes Polynom der Form f =
X + a, a ∈ {0, 1, . . . , k}. Mit der Aussage (b) in Lemma 8.14 folgt dann schließlich
die Behauptung für alle f ∈ Q. Wegen

(X + a)n ≡ X n + a (mod (n, X r ’ 1)) für alle a ∈ {0, 1, . . . , k}
gilt auch

(X + a)n ≡ X n + a (mod (p, X r ’ 1)) für alle a ∈ {0, 1, . . . , k} .
Nach Lemma 8.9 gilt (X + a) p ≡ X p + a (mod (p)) für alle betrachteten a (für
die Richtung ’ in Lemma 8.9 war die Einschr¤nkung ggT(a, n) = 1 nicht nötig),
also gilt auch

(X + a) p ≡ X p + a (mod (p, X r ’ 1)) für alle a ∈ {0, 1, . . . , k} .
Diese Kongruenz besagt, dass es Polynome f , g ∈ Z[X] mit

(X + a) p ’ (X p + a) = p f + (X r ’ 1) g
gibt. Wir fassen diese Kongruenz nun als Kongruenz über Z p [X] auf, indem wir
modulo p rechnen. Wir ersetzen also a, 1, p ∈ Z der Reihe nach durch a, 1, p =
0 ∈ Z p . Es folgt

(X + a) p ≡ X p + a (mod (X r ’ 1)) für alle a ∈ {0, 1, . . . , k} .
Daher ist p introspektiv für X + a, a ∈ {0, 1, . . . , k}, und alle r ∈ N.
Weiterhin erhalten wir für alle a ∈ {0, 1, . . . , k}:
n ·p n ·p n
(X + a) p ≡ (X + a)n ≡ (X n + a) ≡ X p + a ≡ (X p + a) p (mod (p, X r ’ 1)) .
·p
n n
Um diese letzte Kongruenz X p + a ≡ (X p + a) p (mod (p, X r ’ 1)) einzusehen,
gehe man wie im Beweis von ’ zu Lemma 8.9 vor. Wir wenden diesen Trick
·p
n
mit der Binomialformel erneut an und erhalten aus der Kongruenz (X + a) p ≡
n
(X + a) p (mod (p, X r ’ 1)) nun
p

p
n n
(X + a) p ’ (X p + a) ≡ 0 (mod (p, X r ’ 1)) .

Modulo p gerechnet, besagt diese letzte Kongruenz, dass das Polynom X r ’ 1 ∈
p
n n
Z p [X] ein Teiler des Polynoms (X + a) p ’ (X p + a) ∈ Z p [X] ist. Und nun
kommt Lemma 8.15 ins Spiel, es gilt:
n n
(X + a) p ≡ (X p + a) (mod (X r ’ 1)) .
Somit ist also auch n introspektiv für alle X + a, a ∈ {0, 1, . . . , k}, und r ∈ N.
p
Nun beachte man die Aussagen (a) und (b) in Lemma 8.14.
8.4 Der AKS-Test * 161

8.4.5 Die Korrektheit des AKS-Algorithmus

Im Folgenden benutzen wir die Nummerierung (1) “ (5) der Schritte im AKS-
Algorithmus auf Seite 156. Wir begründen die Korrektheit des Algorithmus, in-
dem wir zeigen:

Satz 8.17
Es ist n genau dann eine Primzahl, wenn der AKS-Algorithmus „n ∈ P“ ausgibt.

Beweis. ’: Ist n eine Primzahl, so terminiert der Algorithmus im Schritt (5).
⇐: Der Algorithmus ende bei (5). Wir führen den Beweis in mehreren Schritten.
(i) Es existiert ein Primteiler p von n mit p ≡ 1 (mod r) und p > r.
Würde n¤mlich für jeden Primteiler p von n die Kongruenz p ≡ 1 (mod r) gel-
ten, so würde im Widerspruch zu (2) auch n ≡ 1 (mod r) gelten. Aufgrund von
Schritt (3) und Lemma 8.12 gilt p > r. Damit ist (i) begründet.
Wir werden in den n¤chsten Schritten zeigen, dass n außer p keinen weiteren
Primteiler besitzt. Nach Schritt (1) des Algorithmus ist dann n = p; so folgt also
die Behauptung. Dazu begründen wir zun¤chst:

⊆ Zr gilt < |G| < r.
n 2
(ii) Für die Gruppe G := p, p
Man beachte zun¤chst, dass wegen Schritt (2) im Algorithmus die Zahlen p und

p beide zu r teilerfremd sind, sodass p, p ∈ Z r gilt. Da G eine Untergruppe von
n n

Zr ist (vgl. die Bemerkung auf Seite 96), gilt natürlich |G| < r. Das Element n =
p n liegt in G. Folglich liegen auch alle Potenzen von n in G, d. h. n ⊆ G. Wegen
p
o(n)mod r > 2 (siehe Schritt (2) im AKS-Algorithmus) folgt die Ungleichung <
2

|G|. Damit ist (ii) begründet.
— —
Nach (i) gilt p = 1 ∈ Zr . Da Zr eine endliche Gruppe ist, existiert nach Lemma
6.1 ein s ∈ N mit ps = 1, d. h. ps ≡ 1 (mod r). Wir setzen q := ps und erhalten

r | q ’1.

Wir betrachten nun den endlichen Körper F q mit genau q Elementen (siehe Satz
3.10), wegen q = ps enth¤lt F q den Körper Z p . Die multiplikative Gruppe F — des
q
endlichen Körpers F q ist nach Lemma 6.12 zyklisch. Die Ordnung dieser (end-
lichen) zyklischen Gruppe F — ist q ’ 1. Da r ein Teiler von q ’ 1 ist, existiert
q
nach Lemma 6.6 ein Element ξ ∈ F — mit der Ordnung r. Im Folgenden spielt die
q
Gruppe

H := {ξ + a ; a = 0, . . . , k} = ξ, ξ + 1, . . . , ξ + k ⊆ F — mit k := r
q

eine entscheidende Rolle. Wir zeigen:
|G| + k
(iii) Es gilt |H| ≥ für G aus (ii).
k+1
162 8 Primzahltests

Zur Begründung von (iii) betrachten wir die Menge

k
∏ (X + a)ea ;
f= ea ∈ N0 , deg f < |G| ⊆ Z p [X] .
P :=
a=0

Man beachte, dass f (ξ) ∈ H für jedes f ∈ P. Wir begründen, dass die Abbildung

¦ : P ’ H , f ’ f (ξ)

injektiv ist, es folgt dann |P| ¤ |H|: Es seien f 1 , f 2 ∈ P mit f 1 (ξ) = f 2 (ξ) gew¤hlt.
Nach (4) des AKS-Algorithmus sind wegen Lemma 8.16 die Zahlen m = ps ( n )t p
mit ganzen Zahlen s, t ≥ 0 introspektiv für f i und r. Wir erhalten damit

f i (X)m ≡ f i (X m ) (mod (X r ’ 1)) , d. h. f i (X)m ’ f i (X m ) = g (X r ’ 1)

für ein g ∈ Z[X]. Wir setzen ξ in X ein und beachten o(ξ) = r, d. h. ξ r ’ 1 = 0:

(—) f 1 (ξ m ) = f 1 (ξ)m = f 2 (ξ)m = f 2 (ξ m ) .

Somit ist ξ m eine Nullstelle des Polynoms f 1 ’ f 2 . Wir begründen nun, dass das
Polynom f 1 ’ f 2 vom Grad < |G| mindestens |G| verschiedene Nullstellen im
Körper F q besitzt. Damit kann f 1 ’ f 2 nur das Nullpolynom sein, d. h. f 1 = f 2 ,
und damit ist die Injektivit¤t von ¦ gezeigt.
Es seien a und b verschiedene Elemente aus G:
t v
n n —
a= , b= ∈ Zr .
ps pu
p p

Ohne Einschr¤nkung seien a und b die kleinsten positiven Repr¤sentanten der
Nebenklassen a und b. Da a und b verschieden und kleiner als die Ordnung r von
ξ sind, gilt
ps ( n )t pu ( n )v
= ξa = ξb = ξ
ξ .
p p


Folglich sind ξ a und ξ b verschiedene Nullstellen von f 1 ’ f 2 . Daher hat das Po-
lynom f 1 ’ f 2 mindestens |G| viele Nullstellen, sodass ¦ injektiv ist. Bisher ist
gezeigt |H| ≥ |P|. Nun begründen wir

|G| + k
|P| = .
k+1

Aus k ¤ r < r < p (man beachte (i) und (ii)) folgt, dass die k + 1 Monome
X + a ∈ Z p [X] mit a ∈ {0, 1, . . . , k} verschieden sind. Folglich sind die beiden
Mengen P und T = (e0 , e1 , . . . , ek ) ∈ N0 ; ‘k ea < |G| gleichm¤chtig, so-
k+1
a=0
dass gilt
|H| ≥ |P| = |T| .
8.4 Der AKS-Test * 163

Wir zeigen nun noch
|G| + k
|T| = .
k+1
Hieraus folgt dann die Behauptung in (iii). Dazu ordnen wir jeder (k + 1)-
elementigen Teilmenge {x0 , x1 , . . . , xk } von {1, . . . , |G| + k} (wobei wir ohne Ein-
schr¤nkung x0 < x1 < · · · < xk setzen) ein Tupel (e0 , e1 , . . . , ek ) zu, indem wir
die ei aus den folgenden Gleichungen gewinnen:

e0 + 1 = x 0 , e0 + e1 + 2 = x 1 , . . . , e0 + e1 + · · · + e k + k + 1 = x k .

Da xk ¤ |G| + k, liegt das (k + 1)-Tupel (e0 , e1 , . . . , ek ) in der Menge T. Damit
haben wir eine Abbildung von der Menge aller (k + 1)-elementigen Teilmengen
von {1, . . . , |G| + k} in T erkl¤rt. Diese Abbildung ist offenbar bijektiv. Folglich
sind die beiden Mengen P und T gleichm¤chtig und (iii) ist begründet.
Als N¤chstes begründen wir:

(iv) |H| > n |G| .
In der folgenden Ungleichungskette beachte man der Reihe nach die Ungleichun-
gen bzw. Gleichungen |G| ≥ |G| + 1 (siehe (ii)), ( a+b ) = ( a+b ) für alle
a
b
a, b ∈ N, k ≥ |G| (siehe (ii)), ( 2a+1 ) > 2a+1 für alle a ∈ N >1 (siehe Aufga-
a
be 8.7) und schließlich = log2 n + 1:
⎛ ⎞
|G| + 1 + k
(iii) |G| + k |G| + 1 + k
=⎝ ⎠
|H| ≥ ≥
k+1 |G|
k+1
⎛ ⎞
√ √ √
|G| + 1
2 |G| +1 |G|
= (2 ) |G|
⎝ ⎠>2
≥ ≥2
|G|
√ √ √
log2 n +1 |G| |G|
= n |G| .
= (2 ) ≥ (2 )
log2 n


Damit ist (iv) begründet. Schließlich zeigen wir:
(v) Die Zahl n besitzt außer p keine weiteren Primteiler.
Angenommen, n besitzt einen weiteren Primteiler. Wir zeigen, dass dann |H| ¤

n |G| . Dazu betrachten wir die Menge
t
n
; 0 ¤ s, t ¤ |G|
s
J := .
p
p

t t
= ps , falls (s, t) = (s , t ), sodass
n n
Da n keine Potenz von p ist, gilt ps p p

2
|J | = |G| + 1 > |G| .
164 8 Primzahltests

Hiernach muss es verschiedene Zahlen m1 , m2 ∈ J , m1 = m2 , geben, die aber
modulo r kongruent sind, m1 ≡ m2 (mod r). Ohne Einschr¤nkung sei m1 > m2 ,
und m1 ’ m2 = r m mit einem m ∈ Z. Es gilt nun wegen

X m1 ’ X m2 = X m2 (X m1 ’m2 ’ 1) = X m2 (X r m ’ 1) = X m2 (X r ’ 1) g

für das Polynom g = X r(m’1) + X r(m’2) + · · · + X r + 1 ∈ Z[X] die Kongruenz

X m1 ≡ X m2 (mod (X r ’ 1)) .

Zu h ∈ H existiert ein Polynom f ∈ ∏k (X + a)ea ; ea ∈ N0 ⊆ Z p [X] mit
a=0
h = f (ξ). Es folgt wie beim Beweis der Gleichung (—)

f (X)m1 ≡ f (X m1 ) ≡ f (X m2 ) ≡ f (X)m2 (mod (X r ’ 1)) ,

also hm1 = hm2 . Daher ist h Nullstelle des Polynoms Q := Y m1 ’ Y m2 ∈ F p [Y].
Weil das für alle Elemente aus H gilt, und weil Q = 0 ist, folgt

√ √ √
|G|
n |G| |G|
¤ n |G| .
|H| ¤ deg(Q) = m1 ¤ ¤n
p
p

Das ist ein Widerspruch zu (iv). Damit ist (v) begründet.
Wegen (v) ist n eine Potenz von p. Und nun beachte man Schritt (1) im AKS-
Algorithmus, wonach n keine echte Potenz ist. Es folgt n = p.

Bemerkung
Unsere krude Analyse aus Lemma 8.10 und die Absch¤tzung r ¤ 5 führen auf
eine Laufzeitabsch¤tzung des beschriebenen AKS-Algorithmus von O( 18 ). Ge-
nauere Analysen und Modi¬kationen liefern wesentlich bessere Laufzeiten.


8.5 Vergleich der Primzahltests

Wir geben eine Übersicht über die behandelten Primzahltests:

Test Art Aufwand Bemerkung
deterministisch exponentiell nur für kleine Zahlen
Probedivision
probabilistisch polynomial kein echter Primzahltest
Fermat
probabilistisch polynomial das Mittel der Wahl
Miller-Rabin
deterministisch polynomial theoretische Bedeutung
AKS

Die Probedivison wird benutzt, um kleine Primteiler einer Zahl zu ¬nden. Der
Fermat-Test wird in der Praxis kaum benutzt, das Prinzip aber ist wesentlich für
die meisten bekannten Primzahltests. Der Miller-Rabin-Test ist das Mittel der Wahl
8.5 Vergleich der Primzahltests 165

für Primzahlen, wie sie etwa beim RSA-Verfahren benutzt werden, obwohl der
Test nur probabilistisch ist. Der Miller-Rabin-Test ist n¤mlich deutlich schneller
als der AKS-Test, und die Fehlerwahrscheinlichkeit von 4’k nach k Iterationen ist
nach hinreichend vielen Iterationen genügend klein. Der AKS-Test hat eine sehr
wichtige theoretische Bedeutung: Es gibt einen deterministischen Primzahltest
mit polynomialer Laufzeit. In der Sprache von Kapitel 4 heißt das: Das mathema-
tische Problem „prüfe, ob n eine Primzahl ist“ liegt in der Komplexit¤tsklasse P .



Aufgaben
8.1 Gibt es eine natürliche Zahl a = 1, sodass n = 15 starke Pseudoprimzahl
zur Basis a ist?
Welche natürlichen Zahlen zwischen 2 und 14 sind Zeugen für die Zusammen-
gesetztheit von n = 15?
8.2 Es sei n := 225593397919. Wie man beispielsweise mit Maple überprüfen
kann, ist
n = 2 207 · 6 619 · 15 443
die Primfaktorzerlegung von n.
(a) Schreiben Sie in einer Programmiersprache/-umgebung Ihrer Wahl ein Com-
puterprogramm, das den Fermat™schen Primzahltest für obiges n und a =
2, 3, . . . , 1 000 durchführt. Was f¤llt Ihnen bei den Ergebnissen der Tests auf?
(b) Versuchen Sie, die Ergebnisse aus (a) zu erkl¤ren.
Bestimmen Sie die kleinste Pseudoprimzahl zur Basis 2.
8.3
8.4 Begründen Sie: Sind p1 = 6 u1 + 1, p2 = 12 u2 + 1, p3 = 18 u3 + 1 mit
u1 , u2 , u3 ∈ N Primzahlen, so ist c = p1 p2 p3 eine Carmichael-Zahl.
8.5 Begründen Sie die in dem Beispiel auf Seite 153 gemachte Aussage, dass die
Ideale von Z genau die Mengen (k) = k Z, k ∈ N0 , sind.
8.6 Geben Sie einen polynomialen Algorithmus an, der prüft, ob eine natürliche
Zahl n der L¤nge = log2 (n) + 1 Potenz einer anderen natürlichen Zahl ist.
Gehen Sie wie folgt vor:
(a) Geben Sie ein möglichst kleines Intervall an, in dem alle möglichen Exponen-
ten liegen.
(b) Es sei e ein möglicher Exponent, d. h., n = de mit einem zu bestimmenden
’1
d ∈ N. Zeigen Sie zuerst 2 e ¤ d < 2 e und wenden Sie ein modi¬ziertes
Bisektionsverfahren an.
Zeigen Sie mit Induktion oder anders (2a+1) > 2a+1 für alle a ∈ N >1 .
8.7 a
9 Die Verfahren von Dif¬e und
Hellman, ElGamal und Rabin

Symmetrische Verschlüsselungsverfahren sind im Allgemeinen ef¬zienter als
Public-Key-Verfahren. Eine Möglichkeit, dies auszunutzen, aber dennoch das
Problem der Schlüsselverwaltung zu bew¤ltigen, haben wir bereits unter dem
Stichwort Hybridverfahren kennengelernt: Chiffriere eine Nachricht mit einem (ef-
¬zienten) symmetrischen Verfahren und den (kurzen) Schlüssel zum Dechiffrie-
ren dieser Nachricht mit einem Public-Key-Verfahren, und sende dann diese bei-
den Teile an den Empf¤nger (siehe Abschnitt 7.1.5).
Im vorliegenden Kapitel besprechen wir eine weitere trickreiche Variante, einen
Schlüssel über einen unsicheren Kanal auszutauschen, um dann die Kommuni-
kation mit einem symmetrischen Verfahren sichern zu können.
Beim Dif¬e-Hellman-Schlüsselaustausch wird ein geheimer Schlüssel über eine öf-
fentliche, nicht gesicherte Leitung ausgetauscht. Obwohl ein Angreifer den Aus-
tausch von Teilen des geheimen Schlüssels beobachten kann, ist er im Allgemei-
nen nicht in der Lage, aus diesen Teilen den Schlüssel selbst zu erzeugen. Die
Sicherheit des Verfahrens ist mit der Schwierigkeit des diskreten Logarithmen-
problems verbunden.
Das ElGamal-Verschlüsselungsverfahren ist ein Public-Key-Verfahren, das mit dem
Schlüsselaustausch von Dif¬e-Hellman zusammenh¤ngt. Daher ist auch die Si-
cherheit des ElGamal-Verfahrens an die Schwierigkeit des diskreten Logarith-
menproblems geknüpft. W¤hrend das Public-Key-Verfahren RSA in der Halb-
gruppe Z n realisiert ist, l¤sst sich das ElGamal-Verfahren in beliebigen endlichen
abelschen Gruppen implementieren. Das ElGamal-Verfahren auf einer elliptischen
Kurve “ das ist eine endliche abelsche Gruppe (siehe Kapitel 13) “ ist die derzeit
wohl bestuntersuchte Alternative zum RSA-Verfahren.
Als weiteres Public-Key-Verfahren stellen wir in diesem Kapitel das Rabin-Ver-
fahren vor. Der öffentliche Schlüssel n dieses Verfahrens ist ein Produkt zweier
Primzahlen. Das Rabin-Verfahren ¬ndet kaum praktische Anwendung, aber es
ist dafür von theoretischem Interesse: Es l¤sst sich zeigen, dass das Brechen des

<< . .

. 21
( : 33)



. . >>