Cryptography Reference
In-Depth Information
J
,
m
1
Hiernach muss es verschiedene Zahlen
m
1
,
m
2
∈
=
m
2
, geben, die aber
≡
(
)
>
modulo
r
kongruent sind,
m
1
m
2
mod
r
. Ohne Einschränkung sei
m
1
m
2
,
und
m
1
−
m
2
=
rm
mit einem
m
∈
Z
. Es gilt nun wegen
X
m
1
X
m
2
X
m
2
X
m
1
−
m
2
X
m
2
X
rm
X
m
2
X
r
−
=
(
−
1
)=
(
−
1
)=
(
−
1
)
g
X
r
(
m
−
1
)
+
X
r
(
m
−
2
)
+
···
+
X
r
für das Polynom
g
=
+
1
∈
Z
[
X
]
die Kongruenz
X
m
1
X
m
2
X
r
≡
(
mod
(
−
1
))
.
∈
N
0
k
a
e
a
∈
∈
(
+
)
⊆
Z
p
[
]
Zu
h
H
existiert ein Polynom
f
∏
X
a
;
e
a
X
mit
=
0
=
(
ξ
)
(
∗
)
h
f
. Es folgt wie beim Beweis der Gleichung
m
1
X
m
1
X
m
2
m
2
X
r
(
)
≡
(
)
≡
(
)
≡
(
)
(
(
−
))
f
X
f
f
f
X
mod
1
,
also
h
m
1
h
m
2
. Daher ist
h
Nullstelle des Polynoms
Q
:
Y
m
1
Y
m
2
=
=
−
∈
F
p
[
]
Y
.
Weil das für alle Elemente aus
H
gilt, und weil
Q
=
0 ist, folgt
√
|
G
|
n
p
p
√
|
G
|
n
√
|
G
|
n
√
|
G
|
.
|
|≤
(
)=
≤
≤
≤
H
deg
Q
m
1
Das ist ein Widerspruch zu (iv). Damit ist (v) begründet.
Wegen (v) ist
n
eine Potenz von
p
. Und nun beachte man Schritt (1) im AK
S-
Algorithmus, wonach
n
keine echte Potenz ist. Es folgt
n
=
p
.
Bemerkung
Unsere krude Analyse aus Lemma 8.10 und die Abschätzung
r
5
führen auf
eine Laufzeitabschätzung des beschriebenen AKS-Algorithmus von
O
≤
18
(
)
. Ge-
nauere Analysen und Modifikationen liefern wesentlich bessere Laufzeiten.
8.5 Vergleich der Primzahltests
Wir geben eine Übersicht über die behandelten Primzahltests:
Test
Art
Aufwand
Bemerkung
Probedivision
deterministisch
exponentiell
nur für kleine Zahlen
Fermat
probabilistisch
polynomial
kein echter Primzahltest
Miller-Rabin
probabilistisch
polynomial
das Mittel der Wahl
AKS
deterministisch
polynomial
theoretische Bedeutung
Die
Probedivison
wird benutzt, um kleine Primteiler einer Zahl zu finden. Der
Fermat-Test
wird in der Praxis kaum benutzt, das Prinzip aber ist wesentlich für
die meisten bekannten Primzahltests. Der
Miller-Rabin-Test
ist das Mittel der Wahl
