Cryptography Reference
In-Depth Information
Mit zunehmendem Grad eines irreduziblen Polynoms wird die Bestimmung der
Kodewortlänge immer aufwendiger. Eine schnelle Lösung bietet die Zerlegung
von
p
max
=2
−
1
in Primfaktoren mit
p
max
=
i
p
i
,p
i
∈
P
.
x
p
max
mod
M
(
x
)
liefert bei irreduziblen Polynomen immer den Rest 1.
Die Kodewortlänge kann
immer nur gleich dem Wert eines Primfaktors oder ein Produkt von Prim-
faktoren sein, damit gilt auch immer:
n | p
max
.
Es ist daher ausreichend, die
Polynomreste nur für diese Exponenten zu berechnen. Ergibt sich für einen Po-
lynomrest der Wert 1, ist
n
durch den Wert des Exponenten bestimmt.
M
(
x
)
ist primitiv, wenn
nur
für
x
p
max
der Polynomrest 1 ist und damit
n
=
p
max
gilt.
Ist
p
max
eine Primzahl, dann ist das irreduzible Polynom immer auch primitiv.
k
1
Beispiel 8.5.2
Für
M
(
x
)=
x
6
+
x
4
+
x
2
+
x
+1
ist der Kodeparameter
n
zu bestimmen.
Lösung:
p
max
=2
6
−
1=63
,
p
max
∈
P
−→
p
max
=3
·
3
·
7
Polynomreste:
x
3
mod
M
(
x
)=
x
3
x
7
mod
M
(
x
)=
x
5
+
x
3
+
x
2
+
x
x
3
·
3
mod
M
(
x
)=
x
4
+
x
2
+
x
x
3
·
7
mod
M
(
x
)=1
−→
n
=
p
=21
,M
(
x
)
ist nicht primitiv
.
8.5.1.2 Erweiterungskörper und Minimalpolynome
Bei zyklischen Kodes leitet sich der Minimalabstand
d
min
aus der Anzahl auf-
einanderfolgender Nullstellen des Generatorpolynoms
g
(
x
)
ab.
Die Bestimmung einer Nullstelle erscheint zunächst als sehr einfach. Ein Po-
lynom
P
(
x
)
über dem Körper
GF
(2)
mussnurbzgl.derElemente
x ∈ GF
(2)
untersucht werden. Im folgenden Beispiel wird dabei ein Problem sichtbar.
Beispiel 8.5.3
Es sind die Nullstellen für das Polynom
P
(
x
)=
x
4
+
x
+1
in
GF
(2)
zu be-
stimmen.
Es gilt:
P
(
x
=1)=1
und
P
(
x
=0)=1
.
Das Polynom
P
(
x
)
hat in
GF
(2)
keine Nullstelle.
P
(
x
)
ist nicht in Linearfak-
toren zerlegbar und damit über
GF
(2)
irreduzibel.
Ein irreduzibles Polynom über einem Grundkörper
GF
(2)
,grad
P
(
x
)
>
1
vo-
rausgesetzt, hat auf jeden Fall keine Nullstelle in
GF
(2)
.
12
12
Allerdings ist die Nullstellenberechnung für den Nachweis, ob ein Polynom irreduzibel
ist oder nicht, nur eine notwendige Bedingung. Ein Produkt aus irreduziblen Polynomen
(grad
P
i
(
x
)
>
1
)hatin
GF
(2)
auch keine Nullstelle.
