Cryptography Reference
In-Depth Information
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
≡
(
)
>
r.
Würde nämlich für jeden Primteiler
p
von
n
die Kongruenz
p
1
mod
r
und 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:
p
,
p
n
⊆
Z
r
2
=
< |
| <
(ii)
Für die Gruppe G
:
gilt
G
r.
Man beachte zunächst, dass wegen S
chri
tt (2) im Algorithmus die Zahlen
p
und
n
∈
Z
r
n
p
p
beide zu
r
teilerfremd sind, sodass
p
,
gilt. Da
G
eine Untergruppe von
Z
r
ist (vgl. die Bemerkung auf Seite 96), gilt natürlic
h
|
G
| <
r
. D
as
Element
n
=
p
p
liegt in
G
. Folglich liegen auch alle Potenzen von
n
in
G
,d.h.
⊆
n
G
. Wegen
2
(siehe Schritt (2) imAKS-Algorithmus) folgt die Ungleichung
2
(
)
mod
r
>
<
o
n
|
. Damit ist (ii) begründet.
Nach (i) gilt
p
G
|
∈
Z
r
.Da
Z
r
=
1
eine endliche Gruppe ist, existiert nach Lemma
mit
p
s
1, d. h.
p
s
p
s
und erhalten
∈
N
=
≡
(
)
=
6.1 ein
s
1
mod
r
. Wir setzen
q
:
r
|
q
−
1.
Wir betrachten nun den endlichen Körper
F
q
mit genau
q
Elementen (siehe Satz
p
s
enthält
F
q
des
=
3.10), wegen
q
F
q
den Körper
Z
p
. Die multiplikative Gruppe
endlichen Körpers
F
q
ist nach Lemma 6.12 zyklisch. Die Ordnung dieser (end-
lichen) zyklischen Gruppe
F
q
−
−
ist
q
1. Da
r
ein Teiler von
q
1 ist, existiert
ξ ∈
F
q
mit der Ordnung
r
. Im Folgenden spielt die
nach Lemma 6.6 ein Element
Gruppe
=
√
r
⊆
F
q
mit
k
:
H
:
=
{
ξ
+
a
;
a
=
0, . . . ,
k
}
=
ξ
,
ξ
+
1, . . . ,
ξ
+
k
eine entscheidende Rolle. Wir zeigen:
für G aus
|
|
+
G
k
|
|≥
(
)
(iii)
Es gilt
H
ii
.
k
+
1
