Cryptography Reference
In-Depth Information
Umweitere Aussagen über introspektive Zahlen zu gewinnen, benötigen wir die
folgende Aussage.
Lemma 8.15
Es sei f
ein Polynom über einem Körper K. Ist X
r
1
ein Teiler von f
p
,p
∈
K
[
X
]
−
∈
N
,
so teilt X
r
−
1
bereits f , d. h.
X
r
f
p
X
r
−
1
|
⇒
−
1
|
f
.
0 ein Teiler von
X
r
Beweis.
Angenommen, es ist
g
∈
K
[
X
]
mit deg
g
>
−
1, d. h.
X
r
g
s
h
mit einem
h
−
1
=
∈
K
[
X
]
.
Wir leiten die Polynome nach
X
ab und erhalten mit der Produktregel für die
Ableitung:
rX
r
−
1
sg
s
−
1
g
h
g
s
h
.
=
+
1, so hätten wir in
g
einen gemeinsamen Teiler von
X
r
>
−
Wäre
s
1 und seiner
Ableitung
rX
r
−
1
gefunden. Ein solcher gemeinsamer Teiler wäre aber auch ein
Teiler der Differenz
−
1 dieser Polynome. Folglich muss
s
=
1 gelten: Jeder Teiler
g
von
X
r
0 kommt in einfacher Potenz vor, d. h.
X
r
−
>
−
=
···
1 mit deg
g
1
h
1
h
t
mit verschiedenen irreduziblen Polynomen
h
1
,...,
h
t
.
Für jedes dieser
h
i
gilt
h
i
|
f
, wie mehrfaches Anwenden von Lemma 3.7 zeigt.
X
r
Induktiv folgt
f
=
h
1
...
h
t
f
t
=(
−
1
)
f
t
für ein Polynom
f
t
∈
K
[
X
]
, wie b
e-
hauptet.
Nun haben wir alle Zutaten, um das folgende Ergebnis über introspektiven Zah-
len begründen zu können. Wir werden es benötigen, umdie Korrektheit des AKS-
Algorithmus zu zeigen.
Lemma 8.16
Es sei k
∈
N
, und p sei ein Primteiler der natürlichen Zahl n. Falls für jedes a
∈
{
0, 1, . . . ,
k
}
die Kongruenz
n
X
n
n
,
X
r
(
+
)
≡
+
(
(
−
))
X
a
a
mod
1
gilt, so sind alle Elemente der Menge
p
s
n
p
∈
N
0
t
=
J
:
;
s
,
t
k
a
=
0
(
∈
N
0
e
a
∈
=
+
)
⊆
Z
p
[
]
introspektiv für jedes Polynom f
Q
:
X
a
;
e
a
X
und
∈
N
r
.
