Cryptography Reference
In-Depth Information
Beweis.
Wir zeigen, dass
p
und
p
introspektiv für jedes
X
∈
N
sind. Da nach Lemma 8.14 (a) beliebige Produkte introspektiver Zahlen wieder
intro
s
pektiv sind, folgt hieraus die Behauptung für jedes Polynom der Form
f
+
a
∈
Z
p
[
X
]
und
r
=
+
∈{
}
. Mit der Aussage (b) in Lemma 8.14 folgt dann schließlich
die Behauptung für alle
f
X
a
,
a
0, 1, . . . ,
k
∈
Q
. Wegen
n
X
n
n
,
X
r
(
X
+
a
)
≡
+
a
(
mod
(
−
1
))
für alle
a
∈{
0, 1, . . . ,
k
}
gilt auch
n
X
n
p
,
X
r
(
X
+
a
)
≡
+
a
(
mod
(
−
1
))
für alle
a
∈{
0, 1, . . . ,
k
}
.
p
X
p
Nach Lemma 8.9 gilt
(
X
+
a
)
≡
+
a
(
mod
(
p
))
für alle betrachteten
a
(für
⇒
(
)=
die Richtung
in Lemma 8.9 war die Einschränkung ggT
a
,
n
1 nicht nötig),
also gilt auch
p
X
p
p
,
X
r
(
X
+
a
)
≡
+
a
(
mod
(
−
1
))
für alle
a
∈{
0, 1, . . . ,
k
}
.
Diese Kongruenz besagt, dass es Polynome
f
,
g
∈
Z
[
X
]
mit
p
X
p
X
r
(
X
+
a
)
−
(
+
a
)=
pf
+(
−
1
)
g
gibt. Wir fassen diese Kongruenz nun als Kongruenz über
Z
p
[
X
]
auf, in
d
e
m w
ir
∈
Z
=
m
odulo
p
rechnen. Wir ersetzen also
a
,1,
p
der Reihe nach durch
a
, 1,
p
0
∈
Z
p
. Es folgt
p
X
p
X
r
(
X
+
a
)
≡
+
a
(
mod
(
−
1
))
für alle
a
∈{
0, 1, . . . ,
k
}
.
Daher ist
p
introspektiv für
X
+
a
,
a
∈{
0, 1, . . . ,
k
}
, und alle
r
∈
N
.
Weiterhin erhalten wir für alle
a
∈{
0, 1, . . . ,
k
}
:
n
p
·
X
p
·
p
X
p
p
n
X
n
p
p
,
X
r
(
X
+
a
)
≡
(
X
+
a
)
≡
(
+
a
)
≡
+
a
≡
(
+
a
)
(
mod
(
−
1
))
.
n
p
·
p
n
p
p
p
,
X
r
+
≡
(
+
)
(
(
−
))
Um diese letzte Kongruenz
X
a
X
a
mod
1
einzusehen,
gehe man wie im Beweis von
zu Lemma 8.9 vor. Wir wenden diesen Trick
mit der Binomialformel erneut an und erhalten aus der Kongruenz
⇒
n
p
·
p
(
X
+
a
)
≡
X
p
p
p
,
X
r
(
+
a
)
(
mod
(
−
1
))
nun
p
n
p
n
p
p
,
X
r
(
+
)
−
(
+
)
≡
(
(
−
))
X
a
X
a
0
mod
1
.
Modulo
p
gerechnet, besagt diese letzte Kongruenz, dass das Polynom
X
r
−
1
∈
ein Teiler des Polynoms
p
n
p
n
p
Z
p
[
X
]
(
X
+
a
)
−
(
X
+
a
)
∈
Z
p
[
X
]
ist. Und nun
kommt Lemma 8.15 ins Spiel, es gilt:
n
p
n
p
X
r
(
X
+
a
)
≡
(
X
+
a
)(
mod
(
−
1
))
.
Somit ist also auch
p
introspektiv für alle
X
+
a
,
a
∈{
0, 1, . . . ,
k
}
, und
r
∈
N
.
Nun beachte man die Aussagen (a) und (b) in Lemma 8.14.
