Cryptography Reference
In-Depth Information
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
“ 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
∈
P
“ aus, und das ist ein Beweis,
dass die untersuchte Zahl keine Primzahl ist.
Beim AKS-Test werden wir dieses Prinzip wiederfinden. 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
“ 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
∈
P
“ oder „
n
∈
P
∈
N
∈
Z
eine Primzahl und
a
. Mit der Binomialformel erhalten wir:
n
i
a
i
X
n
−
i
n
1
aX
n
−
1
n
n
a
n
−
1
X
n
i
=
0
n
X
n
a
n
.
(
+
)
=
=
+
+
···
+
+
X
a
−
1
Z
[
]
=(
)
Und nun rechnen wir im Polynomring
X
modulo dem Ideal
I
n
, d. h., wir
n
weg, die Vielfache von
n
in
lassen einfach alle Summanden von
(
X
+
a
)
Z
[
X
]
sind, und erhalten:
n
X
n
a
n
(
+
)
≡
+
(
(
))
.
Beachtet man jetzt noch den Satz 6.10 von Fermat, so können wir hierin
a
n
durch
a
ersetzen, da
n
eine Primzahl ist. Damit ist bereits die Richtung
X
a
mod
n
⇒
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
n
X
n
(
+
)
≡
+
(
(
))
X
a
a
mod
n
.
: Angenommen,
n
ist keine Primzahl. Dann sei
p
k
die
maximale Potenz eines (echten) Primteilers
p
von
n
,d.h.
n
Beweis.
Wir begründen
⇐
p
k
r
für eine Prim-
=
zahl
p
und natürliche Zahlen
k
und
r
und
p
r
. Wir betrachten den Binomialko-
effizienten
n
p
n
(
n
−
1
)
···
(
n
−
p
+
1
)
=
∈
N
.
p
(
p
−
1
)
···
1
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.
