Cryptography Reference
In-Depth Information
Der Fundamentalsatz der Algebra sagt aber, dass jedes Polynom mindestens
eine Nullstelle hat, gegebenenfalls in einem anderen Körper, und dass jedes
Polynom
r
-ten Grades sich in genau
r
Teilpolynome ersten Grades, d. h. in
r
Linearfaktoren, zerlegen lässt, i. Allg. unter Zuhilfenahme von Erweiterungs-
elementen
α
j
:
P
(
x
)=
u
r
x
r
+
u
r−
1
x
r−
1
+
...
+
u
1
x
+
u
0
=(
x − α
1
)(
x − α
2
)
...
(
x − α
r
)
(8.27)
mit
r
Grad des Polynoms,
α
j
Nullstellen des Polynoms in einem Erweiterungskörper unter Einbe-
ziehung der Vielfachheiten von Nullstellen.
Ein neues Element
α
wird als Nullstelle eines irreduziblen Polynoms über
GF
(2)
hinzugefügt, welches einem Erweiterungskörper angehört.
Für unsere Betrachtungen heißt das: Auf der Grundlage eines irreduziblen Mo-
dularpolynoms
M
(
x
)
vom Grad
k
1
=
grad
M
(
x
)
über
GF
(2)
entsteht durch
Hinzunahme einer Nullstelle
α
ein endlicher Erweiterungskörper
GF
(2
k
1
)
,d. h.,
k
1
α
ist Nullstelle von
M
(
x
)
und (Erweiterungs-)Element in
GF
(2
)
.ZumEr-
weiterungskörper
GF
(2
k
1
)
gehören dann neben dem Nullelement die Elemente
α
i
−
2)
). Für
α
j
(
j
=1
,
2
, ..., r
)
in Gl. (8.27) stehen die
(zueinander konjugierten) Elemente des Erweiterungskörpers.
(
i
=0
,
1
, ...,
(2
k
1
Beispiel 8.5.4
Für das irreduzible Modularpolynom
M
(
x
)=
x
3
+
x
2
+1
ist der Erweiterungs-
körper
GF
(2
3
)
wie folgt bestimmt.
Elemente
Polynomreste
Koe
zienten der
des
GF
(2
3
)
α
i
mod
M
(
x
=
α
)
Polynomreste
Nullelement
0
000
α
0
1
001
α
1
α
010
α
2
α
2
100
α
3
α
2
+1
101
α
4
α
2
+
α
+1
111
α
5
α
+1
011
α
6
α
2
+
α
110
Anmerkung
:
Dieser Zusammenhang lässt sich auch mit den Beschreibungsmitteln der Rest-
klassen-Algebra erklären: Jeder Polynomrest stellt dabei eine Restklasse bzw.
einen Restklassen-Repräsentanten minimalen Grades (
<k
1
) im Restklassen-
ring modulo
M
(
x
)
dar.
