i
i
main”—2013/4/10—15:19—page124—#136
i
i
i
i
i
i
124 Primzahlerkennung in Polynomialzeit
Damit gilt 2
n
< kgV(n) für alle n 9. Es bleiben noch die Fälle n = 7 und n = 8
zu untersuchen. Dies weisen wir mit den folgenden Rechnungen direkt nach: 2
7
=
128 < 420 = kgV(7)
, 2
8
= 256 < 840 = kgV(8).
4.3 Von kleinen Zahlen und großen Ordnungen
r ggT(n, r ) = 1 definieren wir ord
r
(n) als die Ordnung von n in der multiplikati-
ven Gruppe
(Z/rZ)
,also
ord
r
(n) = min{i |i 1,n
i
1modr }
Bevor wir das eigentliche Verfahren vorstellen, beweisen wir ein technisches Lemma.
Dieses besagt, dass unter gewissen Vora ussetzungen stets eine kleine Zahl
r existiert,
so dass
ord
r
(n) groß ist. Für den Rest des Abschnitts bezeichnet log wie üblich den
Logarithmus zur Basis 2.
Lemma 4.6. Sei
n eine Primzahl und seien m N mit 7 m
2
log n<n.Danngibt
es eine positive Zahl
r m
2
log n mit ord
r
(n) > m.
Beweis. Sei
s =m
2
log n.Dan eine Primzahl und größer als s ist, ist ord
r
(n)
für alle 1 r s definiert. Mit Widerspruch nehmen wir an, dass ord
r
(n) m
für alle 1 r s gilt. Da n prim ist, gibt es für jedes 1 r s ein 1 i m mit
n
i
1modr .Alsoteiltr den Wert n
i
1 und damit auch das Produkt
m
i=1
(n
i
1).
Hieraus folgt, dass
kgV(s) ein Teiler von
m
i=1
(n
i
1) ist. Mit Satz 4.5 ergibt sich
2
s
kgV(s)
m
i=1
(n
i
1)<n
m
2
Also gilt s<m
2
log n. Dies ist ein Widerspruch zur Wahl von s.
Wir wenden dieses Lemma schließlich mit m =log
2
n an.
Satz 4.7. Sei
n>2
25
eine Primzahl. Dann gibt es ein r N mit r log
5
n und
ord
r
(n) > log
2
n.
Beweis. r
n 2
25
ist n>log
5
n,undmitm =log
2
n finden wir nach Lem-
ma 4.6 ein passendes
r mit r log
5
n.
4.4 Der Agrawal-Kayal-Saxena-Primzahltest
Der AKS-Primzahltest arbeitet auf Eingabe n N wie folgt.
(1) Falls
n<2
25
ist, teste n direkt. Ab jetzt gilt n>log
5
n.
(2) Test e, ob
n = m
k
für ein m N und k 2. Ab jetzt gilt zudem n p
k
für alle
Primzahlen
p und k 2.
i
i
main”—2013/4/10—15:19—page125—#137
i
i
i
i
i
i
Der Agrawal-Kayal-Saxena-Primzahltest 125
(3) Suche in dem Bereich log
2
n<r log
5
n eine Zahl r N mit ggT(r , n) = 1
und ord
r
(n) > log
2
n. Wird keine solche Zahl r gefunden (oder finden wir ein
r mit ggT(r , n) = 1), so ist n nach Satz 4.7 keine Primzahl, und wir brechen
hier ab. Ab jetzt sei
r N mit ggT(r , n) = 1 und log
2
n<r log
5
n sowie
ord
r
(n) > log
2
n.
(4) Für alle
a ∈{2,...,r 1} teste, ob ggT(a, n) = 1 gilt. A b jetzt gilt zusätzlich
ggT(a, n) = 1 für alle 1 a r .
(5) Setze
=
)
ϕ(r)log n und teste für alle a ∈{1,...,} die Kongruenz
(X +a)
n
X
n
+a mod (X
r
1,n)
(6) Ist der Test für alle a ∈{1,...,} positiv, so ist n eine Primzahl, ansonsten ist n
zusammengesetzt.
Satz 4.8. Der AKS-Test kann in Polynomialzeit (in der Eingabegröße
log n)durchge-
führt werden und ist korrekt.
Der Rest dieses Abschnitts ist dem Beweis von Satz 4.8 gewidmet. Die Zahl
2
25
ist eine Konstante und hat keinen Einfluss auf die asymptotische Laufzeit. Für jeden
Exponenten
k log n kann man mit binärer Suche testen, ob eine Zahl m mit n =
m
k
existiert. Insbesondere ist der T e st n = m
k
in Polynomialzeit möglich. Die Werte
a, , r sind polynomiell durch log
5
n beschränkt. Der euklidische Algorithmus zum
Test von
ggT(a, n) = 1 ist polynomiell und für jedes Paar (a, r ) kann die Kongruenz
(X +a)
n
X
n
+ a mod (X
r
1,n)
in Polynomialzeit geprüft werden. Für eine Primzahl n sagt der AKS-Test, dass n prim
ist. Dies folgt aus Lemma 4.1 und Satz 4.7. Zu zeigen bleibt noch, dass der Test heraus-
findet, wenn eine Zahl zusammengesetzt ist. Mit Widerspruch nehmen wir daher an,
dass der AKS-Algorithmus ausgibt,
n sei eine Primzahl, obwohl eine Primzahl p<n
existiert, die n teilt. Insgesamt können wir die folgenden Annahmen treffen:
p ist eine Primzahl und p | n
k 1: n p
k
r log
5
n<n
1 a r : ggT(a, n) = 1
log
2
n<ord
r
(n) ϕ(r)
=
)
ϕ(r)log n≤ϕ(r)
0 a : (X + a)
n
X
n
+ a mod (X
r
1,n)
Aus diesen Annahmen werden wir einen Widerspruch ableiten. Sei F der Zerfällungs-
körper des Polynoms
f(X) = X
r
1 über F
p
. Damit ist F ein endlicher Erweiterungs-
körper von
F
p
, in dem das Polynom f(X)in Linearfaktoren zerfällt:
f(X) = X
r
1 =
r
i=1
(X α
i
)

Get Diskrete algebraische Methoden now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.