Cryptography Reference
In-Depth Information
Ein Vergleich der Exponenten liefert
5
5
3
und damit
3
2
−
<
+
(
−
)
<
2
4
1
4.
>
>
Wegen
n
1 ist aber
1. Damit haben wir einen Widerspruch gefunden,
es
5
mit
o
2
existieren.
muss also ein
r
≤
(
n
)
mod
r
>
Aus diesen Überlegungen ergibt sich:
Korollar 8.13
Der AKS-Algorithmus ist polynomial.
8.4.4
Introspektive Zahlen
Zum Beweis der Korrektheit des AKS-Algorithmus benutzen wir eine Eigen-
schaft sogenannter
introspektiver
Zahlen. Ist
p
eine Primzahl, so heißt eine na-
türliche Zahl
m
introspektiv
für ein
f
∈
Z
p
[
X
]
und
r
∈
N
, falls
m
X
m
X
r
(
)
≡
(
)(
(
−
))
f
X
f
mod
1
.
Beispiel
Die Zahl
m
=
=
+
∈
Z
2
[
]
∈
N
2 ist introspektiv für
f
X
1
X
und jedes
r
, da gilt
2
X
2
X
r
(
X
+
1
)
≡
+
1
(
mod
(
−
1
))
.
Lemma 8.14
Es seien p
∈
P
∈
N
eine Primzahl und r
eine natürliche Zahl. Dann gilt:
Sind m
,
m
, so ist auch mm
∈
Z
p
[
]
∈
N
(a)
introspektiv für ein f
X
und r
intro-
spektiv für f und r
∈
N
.
(b)
Ist m introspektiv für f
,
g
∈
Z
p
[
X
]
und r
∈
N
, so ist m auch introspektiv für f g
∈
N
und r
.
Beweis.
(a) Es seien
m
,
m
introspektiv für
f
∈
Z
p
[
]
∈
N
X
und ein
r
. Wir erhalten
dann:
mm
m
X
m
X
r
f
(
X
)
≡
f
(
)
(
mod
(
−
1
))
.
Da
m
introspektiv für
f
und
r
ist, gilt auch
m
X
mm
X
m
X
mr
(
)
≡
(
)(
(
−
))
f
f
mod
1
.
Hieraus folgt
m
X
mm
X
m
X
r
(
)
≡
(
)(
(
−
))
f
f
mod
1
,
da
X
r
X
mr
1 gilt. Das besagt, dass
mm
−
|
−
1
introspektiv für
f
und
r
ist.
(b) Es gilt
m
m
g
m
X
m
X
m
X
m
X
r
(
fg
)(
X
)
≡
f
(
X
)
(
X
)
≡
f
(
)
g
(
)
≡
(
fg
)(
)(
mod
(
−
1
))
.
Das besagt, dass
m
introspektiv für
fg
und
r
ist.
