Cryptography Reference
In-Depth Information
Damit ist aber
p
k
kein Teiler von
n
p
. Es folgt wegen
p
a
:
n
p
a
p
und somit
n
p
a
p
p
k
≡
0
(
mod
(
n
))
.
Und hieraus folgt mit der Binomialformel ein Widerspruch:
n
p
a
p
X
n
−
p
n
X
n
(
X
+
a
)
−
−
a
≡···
+
+
··· ≡
0
(
mod
(
n
))
,
n
p
a
p
X
n
−
p
···
+
+
···
es hat nämlich das in der Mitte stehende Polynom
we-
<
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
n
X
n
(
+
)
≡
+
(
(
))
X
a
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 imAll-
gemeinen alle Koeffizienten von
n
modulo
(
+
)
(
)
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
X
a
n
, sondern modulo dem von
n
und
X
r
(
n
)
in
Z
[
X
]
−
1in
Z
[
X
]
erzeugten
n
,
X
r
Ideal
I
=(
−
1
)
rechnen. Die Zahl
r
∈
N
ist dabei noch näher zu bestimmen.
∈
N
∈
N
Zuerst halten wir fest: Ist
n
eine Primzahl, so gilt für jedes
r
und jedes
a
∈
Z
auch die Kongruenz
n
X
n
(
∗
)(
+
)
≡
+
(
)
X
a
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
3
.
(
∗
)
(
·
)
r
log
n
Beweis.
Nach Lemma 6.15 kann die
n
-te Potenz in
O
(
log
n
)
Operationen des Rin-
X
r
ges
durchgeführt werden. Dazu wird in jedem Schritt eine Di-
vision mit Rest nach
X
r
Z
n
[
X
]
/
(
−
1
)
−
+
1
Koeffizienten des Ergebnisses modulo
n
reduziert. Mit den Lemmata 4.5 und 4.7
erhalten wir
1 durchgeführt, und anschließend werden alle
r
O
2
O
3
,
r
2
O
(
log
n
)
·
O
(
)
·
(
r
+
1
)
(
log
n
)
=
(
r
log
n
)
wie behauptet.
