Cryptography Reference
In-Depth Information
Jedem Element
α
i
)
ist im
Weiteren ein
Minimalpolynom
m
i
(
x
)
mit den folgenden Eigenschaften zu-
geordnet:
1. Das Minimalpolynom eines beliebigen Elements
α
i
ist irreduzibel und vom
Grad
r
aus dem durch
M
(
x
)
definierten Körper
GF
(2
k
1
k
1
.
2. Zu jedem Element
α
i
existiert genau ein Minimalpolynom
m
i
(
x
)
.
3. Das Minimalpolynom des Elements
α
i
ist gleichzeitig das Minimalpolynom
der konjugierten Elemente
α
2
1
i
,
α
2
2
i
, ..., α
2
r−
1
i
mod
p
.
4. Ist
α
i
eine Nullstelle des Minimalpolynoms
m
i
(
x
)
, dann sind die
r
Nullstellen
α
i
,
α
2
1
i
,
α
2
2
i
, ..., α
2
r−
1
i
sämtliche Nullstellen von
m
i
(
x
)
:
m
i
(
x
)=(
x − α
i
≤
)(
x − α
2
1
i
)(
x − α
2
2
i
)
...
(
x − α
2
r−
1
i
)
.
5. Hat das Element
α
i
die Ordnung
p
i
, dann ist das Minimalpolynom
m
i
(
x
)
ein Polynom mit der Periode
p
i
, dabei gilt:
p
i
|
(2
k
1
−
1)
.
Ein Minimalpolynom ist primitiv, wenn
p
i
=2
−
1
ist.
Ist das Modularpolynom
M
(
x
)
primitiv, dann hat das Minimalpolynom
k
1
k
1
2
−
1
bzw. das Element
α
i
die Ordnung
p
i
.
m
i
(
x
)
die Periode
p
i
=
ggT
(2
k
1
−
1
,i
)
6. Das Modularpolynom
M
(
x
)
ist wegen
M
(
x
=
α
1
)=0
das Minimalpolynom
m
1
(
x
)
des Elements
α
1
.
Beispiel 8.5.5
Es sei der Erweiterungskörper
GF
(2
3
)
aus Beispiel 8.5.4 gegeben. Die Ordnung
des Elements
α
ist
p
=2
3
−
1=7
,d.h.,
M
(
x
)
ist ein primitives Polynom.
Für das Element
α
3
ist das Minimalpolynom
m
3
(
x
)
zu bestimmen.
Lösung:
Zunächst sind entsprechend Gl. (8.28) sämtliche Nullstellen des Minimalpoly-
noms
m
3
(
x
)
zu ermitteln (genau
k
1
Nullstellen, da
p
):
Zyklus für
i
=3:
α
3
,α
6
,α
12mod 7
=
α
5
,α
10mod 7
=
α
3
, ...,
d. h.,
m
3
(
x
)
hat die
Nullstellen
α
3
,α
6
und
α
5
. Damit lässt sich
m
3
(
x
)
berechnen:
m
3
(
x
)=(
x
+
α
3
)(
x
+
α
5
)(
x
+
α
6
)
im
GF
(2)
=(
x
2
+
α
5
x
+
α
3
x
+
α
8
)(
x
+
α
6
)
=
x
3
+
x
2
(
α
6
+
α
3
+
α
5
)+
x
(
α
9
+
α
11
+
α
8
)+
α
14
=
x
3
+
x
+1
.
Das Minimalpolynom
m
3
(
x
)
des Elements
α
3
ist primitiv und gleichzeitig Mi-
nimalpolynom der Elemente
α
5
und
α
6
,d.h.
m
3
(
x
)=
m
5
(
x
)=
m
6
(
x
)
.
∈
P
Zur Vollständigkeit der Beschreibung sind abschließend nochmals alle (unglei-
chen) Zyklen des Erweiterungskörpers
GF
(2
3
)
/M
(
x
)=
x
3
+
x
2
+1
aufgeführt: