Cryptography Reference
In-Depth Information
Zur Begründung von (iii) betrachten wir die Menge
f
k
a
=
0
(
X
+
a
)
e
a
=
=
∈
N
0
, deg
f
< |
|
⊆
Z
p
[
]
P
:
;
e
a
G
X
.
Man beachte, dass
f
(
ξ
)
∈
H
für jedes
f
∈
P
. Wir begründen, dass die Abbildung
Φ
:
P
→
H
,
f
→
f
(
ξ
)
injektiv ist, es folgt dann
|
P
|≤|
H
|
: Es seien
f
1
,
f
2
∈
P
mit
f
1
(
ξ
)=
f
2
(
ξ
)
gewählt.
n
p
=
p
s
(
)
t
Nach (4) des AKS-Algorithmus sind wegen Lemma 8.16 die Zahlen
m
≥
mit ganzen Zahlen
s
,
t
0 introspektiv für
f
i
und
r
. Wir erhalten damit
m
X
m
X
r
m
X
m
X
r
(
)
≡
(
)(
(
−
))
(
)
−
(
)=
(
−
)
f
i
X
f
i
mod
1
,d.h.
f
i
X
f
i
g
1
r
∈
Z
[
]
(
ξ
)=
−
=
für ein
g
X
. Wir setzen
ξ
in
X
ein und beachten
o
r
,d.h.
ξ
1
0:
m
m
m
m
(
∗
)
(
ξ
)=
(
ξ
)
=
(
ξ
)
=
(
ξ
)
f
1
f
1
f
2
f
2
.
m
eine Nullstelle des Polynoms
f
1
−
Somit ist
ξ
f
2
. Wir begründen nun, dass das
Polynom
f
1
−
f
2
vom Grad
< |
G
|
mindestens
|
G
|
verschiedene Nullstellen im
−
=
Körper
F
q
besitzt. Damit kann
f
1
f
2
nur das Nullpolynom sein, d. h.
f
1
f
2
,
und dam
i
t ist d
i
e Injektivität von
gezeigt.
Es seien
a
und
b
verschiedene Elemente aus
G
:
Φ
p
s
n
p
t
p
u
n
p
v
∈
Z
r
a
=
,
b
=
.
Ohne Einschrä
n
kun
g
seien
a
und
b
die kleinsten positiven Repräsentanten der
Nebenklassen
a
und
b
.Da
a
und
b
verschieden und kleiner als die Ordnung
r
von
ξ
sind, gilt
p
s
p
t
p
u
p
v
(
)
(
)
a
b
=
ξ
=
ξ
=
ξ
ξ
.
a
und
b
verschiedene Nullstellen von
f
1
−
Folglich sind
ξ
ξ
f
2
. Daher hat das Po-
−
|
|
lynom
f
1
f
2
mindestens
G
viele Nullstellen, sodass
Φ
injektiv ist. Bisher ist
gezeigt
|
H
|≥|
P
|
. Nun begründen wir
|
.
G
|
+
k
|
|
=
P
+
k
1
≤
√
r
Aus
k
<
r
<
p
(man beachte (i) und (ii)) folgt, dass die
k
+
1 Monome
X
+
a
∈
Z
p
[
X
]
mit
a
∈{
0, 1, . . . ,
k
}
verschieden sind. Folglich sind die beiden
gleichmächtig, so-
k
+
1
a
Mengen
P
und
T
=
(
e
0
,
e
1
,...,
e
k
)
∈
N
;
0
e
a
< |
G
|
∑
=
0
dass gilt
|
H
|≥|
P
|
=
|
T
|
.
