Cryptography Reference
In-Depth Information
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.
∈
N
>
1
der Länge
=
+
Eingabe:
n
log
2
n
1.
Ausgabe:
„
n
∈
P
“ oder „
n
∈
P
“.
∈
P
(1)
Teste, ob
n
eine (echte) Potenz ist (vgl. Aufgabe 8.6). Falls ja, so gib „
n
“
aus, sonst fahre fort mit:
2
.
∈
N
(
)
mod
r
>
(2)
Finde
r
minimal mit
o
n
5
. Falls ein solcher existiert, so gib aus
(3)
Teste
n
auf Primteiler
p
≤
∈
P
=
„
n
“, falls
p
n
,
„
n
∈
P
“, sonst.
Andernfalls fahre fort mit:
√
r
(4)
Für
a
=
1, 2, . . . ,
prüfe:
n
X
n
n
,
X
r
(
+
)
≡
+
(
(
−
))
∈
P
Falls
X
a
a
mod
1
, so gib „
n
“ aus, sonst:
∈
P
(5)
Gib „
n
“ aus.
Bevor wir die Korrektheit des Algorithmus beweisen, zeigen wir, dass im Schritt
(2) des Algorithmus die Abschätzung
5
r
≤
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
2
n
−
2
.
∈
N
sei
λ
(
n
)
:
=
kgV
(
1, 2, . . . ,
n
)
. Dann gilt
λ
(
n
)
≥
