Cryptography Reference
In-Depth Information
8.5.1
Ausgewählte algebraische Grundlagen
8.5.1.1 Eigenschaften eines Modularpolynoms
Grundlage für die Bildung des Generatorpolynoms ist ein Modularpolynom
M
(
x
)
über dem Körper
K
=
GF
(2)
(s. a. Abschn. 8.3.3). An dieses Modular-
polynom werden folgende Eigenschaften geknüpft.
1. Das Modularpolynom muss irreduzibel sein.
Definition 8.5.2
Ein Polynom ist
irreduzibel
, wenn es nicht in ein Pro-
dukt von Polynomen zerlegbar ist.
Das Modularpolynom
M
(
x
)
vom Grad
k
1
=
grad
M
(
x
)
bestimmt den Kode-
parameter
n
, d. h., das irreduzible Polynom legt die Kodewortlänge der Kanal-
kodewörter im Alphabet
A
fest. Es gilt der folgende Zusammenhang:
k
1
n
≤
2
−
1
.
(8.26)
Der tatsächliche Wert von
n
lässt sich aus dem Zyklus der Polynomreste über
GF
(2)
mit
x
i
mod
M
(
x
)(
i
=0
,
1
, ..., p
(=
n
))
berechnen. Für einen gewissen
Wert
p
wiederholen sich die Polynomreste, d. h.
x
i
=
x
i
+
p
mod
M
(
x
)
.Dabei
k
1
kann
p
maximal den Wert
(2
−
1)
annehmen.
2. Liefert der Zyklus der Polynomreste eine maximale Periode, dann besitzt
das irreduzible Polynom
M
(
x
)
auch die Eigenschaft, primitiv zu sein.
Definition 8.5.3
Ein
primitives
Polynom vom Grad
k
1
ist irreduzibel und
erzeugt im Zyklus der Polynomreste eine maximale Periode
p
max
=2
k
1
−
1
.
Beispiel 8.5.1
Es ist die mögliche Kodewortlänge
n
zu bestimmen, wenn das Modularpoly-
nom mit
M
(
x
)=
x
3
+
x
2
+1
gegeben ist.
Es gilt:
k
1
=
grad
M
(
x
)=3
−→
n ≤
2
k
1
−
1=7
.
Zyklus der Polynomreste:
x
i
x
i
mod
(
x
3
+
x
2
+1)
x
i
x
i
mod
(
x
3
+
x
2
+1)
x
4
x
2
+
x
+1
x
5
x
+1
x
6
x
2
+
x
x
7
x
0
1
x
1
x
x
2
x
2
x
3
x
2
+1
1
−→
n
=
p
max
=7