Cryptography Reference
In-Depth Information
α
0
α
1
,α
2
,α
4
α
3
,α
6
,α
5
0
1
,
2
,
4
3
,
6
,
5
, in Kurz- bzw. Exponentenschreibweise:
.
Jedes Element des Erweiterungskörpers befindet sich in einem Zyklus. Entspre-
chend der Zyklenlängen sind im Erweiterungskörper zwei Minimalpolynome 3.
Grades und ein Minimalpolynom 1. Grades definiert.
Fassen wir zusammen:
Ein irreduzibles Polynom
M
(
x
)
vom Grad
k
1
mit dem Element
α
als Nullstel-
le erzeugt einen Erweiterungskörper
GF
(2
k
1
Elementen (Nullelement
und Potenzen von
α
). Der Zyklus der Polynomreste im
GF
(2
k
1
)
mit
2
k
1
)
bestimmt die
Ordnung
p
des Elements
α
und damit den Kodeparameter
n
. Jedem Element
des Erweiterungskörpers ist ein Minimalpolynom zugeordnet. Das Minimal-
polynom
m
i
(
x
)
in
GF
(2
k
1
)
ist durch das Element
α
i
und die konjugierten
Elemente
α
2
1
i
,α
2
2
i
, ..., α
2
r−
1
i
mod
p
eindeutig definiert. Die Länge des Zyklus
(
r
k
1
) bestimmt die Anzahl der Nullstellen und den Grad von
m
i
(
x
)
.
Es gilt:
m
i
(
x
)=(
x − α
2
0
i
≤
)(
x − α
2
1
i
)
...
(
x − α
2
r−
1
i
)
.
Ergänzend sei auf folgenden Zusammenhang hingewiesen. Alle Elemente eines
Erweiterungskörpers
GF
(2
k
1
)
sind Nullstellen eines Hauptpolynoms
f
(
x
)
mit:
α
p−
1
)
=(
x
+0)(
x
+
α
0
)(
x
+
α
1
)
...
(
x
+
α
p−
1
)
α
0
)(
x
α
1
)
...
(
x
f
(
x
)=(
x
−
0) (
x
−
−
−
im
GF
(2)
.
Dieser Zusammenhang gilt allgemein für Erweiterungskörper
GF
(
q
k
1
)
mit
q ∈
P
und wird als FERMAT-Theorem bezeichnet. Durch Ausmultiplizieren und
Ersetzen der Potenzen von
α
durch die Polynomreste mod
M
(
α
)
ergibt sich
für das Hauptpolynom
f
(
x
)=
x
p
+1
+
x
=
x
n
+1
+
x
. Lässt man das Nullelement
aus den Betrachtungen heraus, ist das Hauptpolynom mit
f
(
x
)=
x
n
+1
definiert.
n
stellt dabei wieder die realisierbare Kodewortlänge eines durch
ein Modularpolynom erzeugten zyklischen Kodes dar. Im Beispiel 8.5.4 ist
n
=
p
max
=7
, d. h., das Hauptpolynom
f
(
x
)
ist ein Polynom 7. Grades und
lässt sich in genau
7
Teilpolynome ersten Grades zerlegen:
f
(
x
)=(
x − α
0
)(
x − α
1
)(
x − α
2
)(
x − α
3
)(
x − α
4
)(
x − α
5
)(
x − α
6
)
=(
x
+1)(
x
+
α
)(
x
+
α
2
)(
x
+
α
3
)(
x
+
α
4
)(
x
+
α
5
)(
x
+
α
6
)
im
GF
(2)
.
Sieht man sich
f
(
x
)
genauer an, erkennt man die im Erweiterungskörper be-
stimmten Minimalpolynome
m
0
(
x
)
,m
1
(
x
)
,m
3
(
x
)
:
f
(
x
)=(
x
+1)(
x
+
α
)(
x
+
α
2
)(
x
+
α
3
)(
x
+
α
4
)(
x
+
α
5
) (
x
+
α
6
)
=(
x
+1)(
x
3
+
x
2
+1)(
x
3
+
x
+1) =
x
7
+1
.