<< . .

. 20
( : 33)



. . >>

|K| n’1
|A| ¤ |L| = ¤ ’1 .
2 ’1 2
Wir treffen Fallunterscheidungen für .
1. Fall: ≥ 3: Dann gilt |L| ¤ n’1 , wie gewünscht.
4
νν
2. Fall: = 2: Dann gilt n = p11 p22 . Nach Korollar 8.5 ist n keine Carmichael-
Zahl, sodass J = Z — gilt. Also gilt 2 ¤ |Z — /J| = |Z — |/|J| = •(n)/|J|, und
n n n
damit (beachte (1) und (2)):
•(n) |J| |K|
•(n) = |L| ≥ 2 · 1 · 2 · |L| .
|J| |K| |L|
•(n)
Folglich gilt |L| ¤ 4 ¤ n’1 , wie gewünscht.
4
3. Fall: = 1: Es gilt n = pν , ν ≥ 2. Wegen •(n) = pν’1 (p ’ 1) ist p ein Teiler
von •(n). Nach dem Satz 6.8 von Cauchy existiert ein a ∈ Z — mit o(a) = p, d. h.
n
a p = 1. Da p n ’ 1, gilt an’1 = 1, sodass a ∈ J, also {J, a J, . . . , a p’1 J} ⊆ Z — /J.
n
— /J| ≥ p, also |J| ¤ •(n) .
Damit gilt |Z n p
Im Fall p > 3 erhalten wir hieraus das Gewünschte aus |L| ¤ |J| unmittelbar. Es
bleibt der Fall p = 3 zu untersuchen: Es sei n = 3ν mit ν ≥ 2.
Falls ν = 2 ist, ist n = 9 und damit s = 3 und d = 1. Wegen 8 ≡ ’1 (mod 9)
ist 9 eine starke Pseudoprimzahl zur Basis 8, d. h. {1, 8} ⊆ A. Und tats¤chlich
gilt {1, 8} = A, da für alle weiteren a zwischen 1 und 9 gilt a ≡ ±1 (mod 9),
a2 ≡ ’1 (mod 9), a4 ≡ ’1 (mod 9). Es folgt |A| = 2 ¤ 9’1 , wie gewünscht.
4
Nun zum letzten Fall p = 3 und ν > 2: Es gilt o(4)mod33 = 9. Daher gilt auch
o(4)mod3ν ≥ 9, da aus 4r ≡ 1 (mod 3ν ) für r < 9 auch 4r ≡ 1 (mod 33 ) folgte.

Wegen |Z3ν | = •(3ν ) = 2 · 3ν’1 gilt o(4)mod3ν | 2 · 3ν’1 . Da, wie bereits gezeigt
152 8 Primzahltests

o(4)mod3ν ≥ 9 gilt, können wir sagen, dass 3 ein Teiler von o(4)mod3ν ist. Und
weil n ’ 1 = 3ν ’ 1 sicher nicht von 3 geteilt wird, erhalten wir für das Element
4 ∈ Z — sogar 4 ∈ J, da 4n’1 ≡ 1 (mod 3ν ).
n
Wir betrachten nun die Faktorgruppe Z — /J. Diese Gruppe enth¤lt mindestens
n
•(n)
8
die neun verschiedenen Elemente J, 4 J, . . . , 4 J. Damit gilt |J| ¤ 9, wegen
|L| ¤ |J| erhalten wir wieder das Gewünschte.
Wir interpretieren das Ergebnis aus Satz 8.7: Liefert der Miller-Rabin-Test „n ∈
P“ für eine Basis a ∈ {2, . . . , n ’ 1}, so ist die untersuchte ungerade natürliche
Zahl n mit einer Wahrscheinlichkeit kleiner gleich 1 dennoch zusammengesetzt.
4
Nach zehn solchen positiven Tests mit zehn verschiedenen a ist n mit einer Wahr-
scheinlichkeit von kleiner gleich (1/4)10 ≈ 10’6 zusammengesetzt, allgemeiner:

Korollar 8.8
Die Wahrscheinlichkeit dafür, dass n zusammengesetzt ist, obwohl der Miller-Rabin-Test
„n ∈ P“ mit t verschiedenen, zuf¤llig gew¤hlte a ausgibt, ist kleiner als (1/4)t .


Bemerkung
Der Miller-Rabin-Test ist das Mittel der Wahl, um Primzahlen von der Größen-
ordnung 512 Bit, wie sie beim RSA-Verfahren benutzt werden, zu erzeugen.



Der AKS-Test *
8.4
Der AKS-Primzahltest wurde 2002 von Agrawal, Kayal und Saxena veröffent-
licht. N. Kayal und N. Saxena waren damals Studenten. Es handelt sich um den
ersten deterministischen Primzahltest mit polynomialer Laufzeit. Die Veröffent-
lichung war daher eine Sensation. Die Korrektheit des Algorithmus “ an der un-
mittelbar nach der Veröffentlichung verschiedentlich gezweifelt wurde “ wurde
in nur wenigen Tagen von bedeutenden Mathematikern best¤tigt. Das wohl Er-
staunlichste am AKS-Test ist, dass er mit nur wenigen Vorbereitungen von jedem
Mathematikstudenten verstanden werden kann, obwohl Fachleute schon lange
erfolglos nach einem solchen Test gesucht haben.
In diesem Abschnitt sei n ∈ N >1 , und := log2 n + 1 sei die L¤nge von n in
Bin¤rdarstellung. Diese Zahl n wollen wir auf Primalit¤t prüfen.


8.4.1 Ideale in Ringen

Unter einem Ideal eines kommutativen Ringes R versteht man eine Untergruppe
I von (R, +) mit der Eigenschaft I R ⊆ I, d. h.:

a ∈ I, r ∈ R ’ ar ∈ I.
8.4 Der AKS-Test * 153

Im Rahmen des AKS-Testes werden uns Ideale in Polynomringen interessieren.
Dazu erinnern wir an den Polynomring K[X] über einem Ring K, insbesondere
über Z:
k
‘ ai X i ;
f= k ∈ N0 , ai ∈ K für alle i = 0, . . . , k
K[X] := .
i=0

Polynomringe wurden im Abschnitt 3.1.2 eingeführt. Nachfolgend die für alles
weitere wesentlichen Beispiele für Ideale.

Beispiel
Für jedes Element a eines kommutativen Ringes R ist
I = (a) := a R = {a r ∈ R ; r ∈ R}
ein Ideal.
Etwas allgemeiner: Für beliebige Elemente a1 , . . . , ak eines kommutativen Rin-
ges R bildet
I = (a1 , . . . , ak ) := a1 R + · · · + ak R = {a1 r1 + · · · + ak rk ; r1 , . . . , rk ∈ R}
ein Ideal von R “ man nennt es das von a1 , . . . , ak erzeugte Ideal von R.
{0} und R sind Ideale von R “ die sogenannten trivialen Ideale des Ringes R,
man nennt {0} das Nullideal und R das Einsideal von R; es gilt {0} = (0)
und R = (1).
Die Ideale von Z sind genau die Mengen (k) = k Z mit k ∈ N0 . Den Nachweis
dieser Aussage haben wir als Übungsaufgabe gestellt.
Für jedes f ∈ Z[X] ist I = ( f ) = f Z[X] = { f g ; g ∈ Z[X]} ein Ideal des
Polynomrings Z[X] “ dies ist ein Sonderfall des ersten Beispiels.

Wir treffen eine Vereinbarung: Wir schreiben für ein Ideal I eines Ringes R und
Elemente r, s ∈ R
r ≡ s (mod I) :” r ’ s ∈ I
und sagen in diesem Fall, dass r und s kongruent modulo I sind. Diese Schreib-
weise kollidiert nicht mit der bereits vielfach benutzten Schreibweise
a ≡ b (mod k) ” k | a ’ b
für ganze Zahlen a und b. Es gilt n¤mlich:
a ≡ b (mod (k)) ” a ’ b ∈ (k) = k Z ” k | a ’ b ” a ≡ b (mod k) .

Beispiel
Für den kommutativen Ring Z[X] und I = (k) = k Z[X], k ∈ N, gilt etwa
X 3 ’ k X ≡ X 3 (mod I) ,
da die Differenz (X 3 ’ k X) ’ X 3 in I liegt.
154 8 Primzahltests

8.4.2 Die Idee des AKS-Tests

Sowohl beim Fermat-Test wie auch beim Miller-Rabin-Test sind wir von einer
Eigenschaft von Primzahlen ausgegangen:
Wenn n eine Primzahl ist, dann gelten ... gewisse Kongruenzen.
Der Test selbst verl¤uft dann dergestalt, dass man diese Kongruenzen einfach
nachprüft: Sind die Kongruenzen erfüllt, so gibt der Test „n ∈ P“ aus, und das ist
ein Hinweis darauf, dass die untersuchte Zahl eine Primzahl sein könnte. Sind die
Kongruenzen nicht erfüllt, so gibt der Test „n ∈ P“ aus, und das ist ein Beweis,
dass die untersuchte Zahl keine Primzahl ist.
Beim AKS-Test werden wir dieses Prinzip wieder¬nden. Wir zeigen:
Wenn n eine Primzahl ist, dann gilt eine ... noch n¤her zu bestimmende Kongruenz.
Aber es gibt einen wesentlichen Unterschied zum Fermat- und Miller-Rabin-Test:
Liefert der AKS-Test das Ergebnis „n ∈ P“ oder „n ∈ P“ so ist das nicht nur ein
Hinweis, es ist sogar ein Beweis für diese Aussage. Der AKS-Test ist also determi-
nistisch.
Es seien n ∈ N eine Primzahl und a ∈ Z. Mit der Binomialformel erhalten wir:
n
n n n

(X + a) = ai X n’i = X n + a X n’1 + · · · + an’1 X + an .
n
n’1
1
i
i=0

Und nun rechnen wir im Polynomring Z[X] modulo dem Ideal I = (n), d. h., wir
lassen einfach alle Summanden von (X + a)n weg, die Vielfache von n in Z[X]
sind, und erhalten:
(X + a)n ≡ X n + an (mod (n)) .
Beachtet man jetzt noch den Satz 6.10 von Fermat, so können wir hierin an durch
a ersetzen, da n eine Primzahl ist. Damit ist bereits die Richtung ’ des folgenden
Lemmas bewiesen:

Lemma 8.9
Gegeben seien zwei teilerfremde natürliche Zahlen a und n. Die Zahl n ist genau dann
eine Primzahl, wenn im Ring Z[X] gilt
(X + a)n ≡ X n + a (mod (n)) .

Beweis. Wir begründen ⇐: Angenommen, n ist keine Primzahl. Dann sei pk die
maximale Potenz eines (echten) Primteilers p von n, d. h. n = pk r für eine Prim-
zahl p und natürliche Zahlen k und r und p r. Wir betrachten den Binomialko-
ef¬zienten
n (n ’ 1) · · · (n ’ p + 1)
n
= ∈ N.
p (p ’ 1) · · · 1
p
In dem rechten Bruch kürzt sich das p im Nenner mit einem entsprechenden
Faktor von n des Z¤hlers, da die Faktoren n ’ 1, . . . , n ’ p + 1 des Z¤hlers zu p
teilerfremd sind, es gilt n¤mlich
n ’ i ≡ ’i ≡ 0 (mod p) für i = 1, . . . , p ’ 1 .
8.4 Der AKS-Test * 155

n
Damit ist aber pk kein Teiler von . Es folgt wegen p a:
p

np
n
a ≡ 0 (mod (n)) .
pk a p und somit
p p
Und hieraus folgt mit der Binomialformel ein Widerspruch:
n
(X + a)n ’ X n ’ a ≡ · · · + a p X n’p + · · · ≡ 0 (mod (n)) ,
p

n
es hat n¤mlich das in der Mitte stehende Polynom · · · + a p X n’p + · · · we-
p
gen p < n einen Summanden, der nicht Vielfaches von n ist.
Ist für n ∈ N zu entscheiden, ob n eine Primzahl ist, so w¤hle man ein a ∈ Z,
prüfe zun¤chst, ob ggT(a, n) = 1, und teste dann, ob die Kongruenz
(X + a)n ≡ X n + a (mod (n))
erfüllt ist. Falls nicht, so ist n garantiert keine Primzahl. Gilt diese Kongruenz
hingegen, so ist n garantiert eine Primzahl.
Aber in dieser Form ist der Test viel zu rechenaufw¤ndig. Tats¤chlich sind im All-
gemeinen alle Koef¬zienten von (X + a)n modulo (n) zu bestimmen, was einen
exponentiellen Aufwand bedeutet. Die Laufzeit des AKS-Tests aber ist polynomi-
al. Diesen polynomialen Aufwand erreichen wir dadurch, dass wir nicht modulo
dem Ideal (n) in Z[X], sondern modulo dem von n und X r ’ 1 in Z[X] erzeugten
Ideal I = (n, X r ’ 1) rechnen. Die Zahl r ∈ N ist dabei noch n¤her zu bestimmen.
Zuerst halten wir fest: Ist n ∈ N eine Primzahl, so gilt für jedes r ∈ N und jedes
a ∈ Z auch die Kongruenz
(—) (X + a)n ≡ X n + a (mod I) .
Diese Kongruenz kann mit der schnellen Exponentiation ausgewertet werden.
Dabei wird die Laufzeit von r und log n bestimmt. In der Tat gilt folgende grobe
Absch¤tzung.

Lemma 8.10
Die Laufzeit zur Auswertung von (—) ist asymptotisch beschr¤nkt durch O (r · log n)3 .

Beweis. Nach Lemma 6.15 kann die n-te Potenz in O(log n) Operationen des Rin-
ges Z n [X]/(X r ’ 1) durchgeführt werden. Dazu wird in jedem Schritt eine Di-
vision mit Rest nach X r ’ 1 durchgeführt, und anschließend werden alle r + 1
Koef¬zienten des Ergebnisses modulo n reduziert. Mit den Lemmata 4.5 und 4.7
erhalten wir
O(log n) · O(r2 ) · (r + 1) O (log n)2 = O (r log n)3 ,

wie behauptet.
156 8 Primzahltests

Nun taucht ein anderes Problem auf: W¤hrend im Lemma 8.9 „genau dann,
wenn“ steht, haben wir nun wieder nur eine „Wenn ..., dann ...“-Beziehung: Die
Kongruenz (—) kann auch dann für Zahlen a und r erfüllt sein, wenn n keine
Primzahl ist. Ein entsprechender Test scheint also doch wieder probabilistisch zu
sein. Wir werden jedoch zeigen, dass es im Fall, dass n keine Primzahl ist, stets
ein a gibt, sodass die Kongruenz (—) nicht erfüllbar ist.
Der Knackpunkt des AKS-Tests besteht darin, dass es genügt, die Kongruenzglei-
chung (—) für ein kleines r und einen kleinen Bereich für a zu prüfen.
Die Tatsache, dass wir r und die Anzahl der Auswertungen von (—) beschr¤nken
können, bewirkt, dass der Algorithmus polynomial ist.


8.4.3 Der AKS-Algorithmus

Wir formulieren zuerst den AKS-Algorithmus und zeigen dann, dass der Algo-
rithmus das gewünschte Ergebnis liefert.
Eingabe: n ∈ N >1 der L¤nge = log2 n + 1.
Ausgabe: „n ∈ P“ oder „n ∈ P“.

Teste, ob n eine (echte) Potenz ist (vgl. Aufgabe 8.6). Falls ja, so gib „n ∈ P“
(1)
aus, sonst fahre fort mit:

Finde r ∈ N minimal mit o(n)mod r > 2.
(2)

Teste n auf Primteiler p ¤ 5. Falls ein solcher existiert, so gib aus
(3)

„n ∈ P“, falls p = n,
„n ∈ P“, sonst.

Andernfalls fahre fort mit:

Für a = 1, 2, . . . , r prüfe:
(4)
Falls (X + a)n ≡ X n + a (mod (n, X r ’ 1)), so gib „n ∈ P“ aus, sonst:

Gib „n ∈ P“ aus.
(5)

Bevor wir die Korrektheit des Algorithmus beweisen, zeigen wir, dass im Schritt
(2) des Algorithmus die Absch¤tzung

r¤ 5


gilt, sodass also r tats¤chlich klein ist. Für die Begründung benötigen wir das fol-
gende Lemma:

Lemma 8.11
Für n ∈ N sei »(n) := kgV(1, 2, . . . , n). Dann gilt »(n) ≥ 2n’2 .
8.4 Der AKS-Test * 157

Beweis. Für ein N ∈ N betrachten wir das Polynom f = a2N X 2N + · · · + a1 X +
a0 X 0 ∈ Z[X]. Es gilt

2N 2N
1 1 a m
‘ ai ‘ i +i 1 =
f (t) d t = t dt = für ein m ∈ Z .
i
»(2 N + 1)
0 0
i=0 i=0

Nun betrachten wir das spezielle Polynom f = X N (1 ’ X) N , das eine sol-
che betrachtete Form hat. Es gilt für alle 0 < t < 1 die Ungleichungskette
0 < f (t) ¤ 41 “ für die Absch¤tzung nach oben zeige man, dass die Polynom-
N

funktion f (x) = (x (1 ’ x)) N auf dem Intervall [0, 1] ein globales Maximum in
x = 1/2 besitzt. Es folgt
1 1
m
0< f (t) d t = ¤N
»(2 N + 1) 4
0

für ein m ∈ N. Das liefert

»(2N + 1) ≥ 4 N ≥ 2(2N+1)’2 ,

also die Behauptung für ungerade n = 2 N + 1. Wegen

»(2 N + 2) ≥ »(2 N + 1) ≥ 4 N = 2(2N+2)’2

folgt die Behauptung auch für gerade n = 2 N + 2.

Mit diesem Lemma können wir nun zeigen, dass es ein r der gewünschten Grö-
ßenordnung gibt.

Lemma 8.12
Zu n ∈ N >1 der L¤nge = log2 n + 1 mit ggT(n, »( 5 )) = 1 existiert ein r ∈ N
mit r ¤ 5 und o(n)mod r > 2 .

Beweis. Wir nehmen an, dass kein solches r existiert. Dann gilt o(n)mod r ¤ 2 für
jedes r ¤ 5 , denn r und n sind nach Voraussetzung teilerfremd. Das besagt, dass
für jedes r ¤ 5 eine Kongruenz der Form ni ≡ 1 (mod r) für ein i ∈ {1, . . . , 2 }
gilt. Damit erhalten wir für jedes r ¤ 5 :
2 2

∏(n ’ 1) und damit »( ) | ∏(ni ’ 1) .
r| 5
i
i=1 i=1

5 ’2
Wir wenden nun Lemma 8.11 an, wonach »( 5 ) ≥ 2 gilt; wir erhalten:
2 2
( 2 +1)/2
2
5 ’2 ( 2 +1)/2 log2 (n) ( 2 +1)/2
2 3
¤ ∏(n ’ 1) < ∏ n = n =2 ¤2
i i
2 .
i=1 i=1
158 8 Primzahltests

Ein Vergleich der Exponenten liefert
’4 < + ( ’ 1) < 4 .
5 5 3 3 2
2 und damit
Wegen n > 1 ist aber > 1. Damit haben wir einen Widerspruch gefunden, es
muss also ein r ¤ 5 mit o(n)mod r > 2 existieren.
Aus diesen Überlegungen ergibt sich:

Korollar 8.13
Der AKS-Algorithmus ist polynomial.


8.4.4 Introspektive Zahlen

Zum Beweis der Korrektheit des AKS-Algorithmus benutzen wir eine Eigen-
schaft sogenannter introspektiver Zahlen. Ist p eine Primzahl, so heißt eine na-
türliche Zahl m introspektiv für ein f ∈ Z p [X] und r ∈ N, falls
f (X)m ≡ f (X m ) (mod (X r ’ 1)) .

Beispiel
Die Zahl m = 2 ist introspektiv für f = X + 1 ∈ Z2 [X] und jedes r ∈ N, da gilt
(X + 1)2 ≡ X 2 + 1 (mod (X r ’ 1)) .
Lemma 8.14
Es seien p ∈ P eine Primzahl und r ∈ N eine natürliche Zahl. Dann gilt:
Sind m, m introspektiv für ein f ∈ Z p [X] und r ∈ N, so ist auch m m intro-
(a)
spektiv für f und r ∈ N.
Ist m introspektiv für f , g ∈ Z p [X] und r ∈ N, so ist m auch introspektiv für f g
(b)
und r ∈ N.

Beweis. (a) Es seien m, m introspektiv für f ∈ Z p [X] und ein r ∈ N. Wir erhalten
dann:
f (X)mm ≡ f (X m )m (mod (X r ’ 1)) .
Da m introspektiv für f und r ist, gilt auch

f (X m )m ≡ f (X mm ) (mod (X mr ’ 1)) .
Hieraus folgt
f (X m )m ≡ f (X mm ) (mod (X r ’ 1)) ,
da X r ’ 1 | X mr ’ 1 gilt. Das besagt, dass m m introspektiv für f und r ist.
(b) Es gilt
( f g)(X)m ≡ f (X)m g(X)m ≡ f (X m ) g(X m ) ≡ ( f g)(X m ) (mod (X r ’ 1)) .
Das besagt, dass m introspektiv für f g und r ist.
8.4 Der AKS-Test * 159

Um weitere Aussagen über introspektive Zahlen zu gewinnen, benötigen wir die
folgende Aussage.

Lemma 8.15
Es sei f ∈ K[X] ein Polynom über einem Körper K. Ist X r ’ 1 ein Teiler von f p , p ∈ N,
so teilt X r ’ 1 bereits f , d. h.

Xr ’ 1 | f p ’ Xr ’ 1 | f .

Beweis. Angenommen, es ist g ∈ K[X] mit deg g > 0 ein Teiler von X r ’ 1, d. h.

<< . .

. 20
( : 33)



. . >>