Cryptography Reference
In-Depth Information
where
m
α
i
(
x
)
is the minimal polynomial with coecients in field
F
2
asso-
ciated with
α
j
, and S.C.M. is the Smallest Common Multiple.
It is shown in the appendix that a polynomial with coecients in
F
2
having
α
j
as its root also has
α
2
j
as its root. Thus, the minimal polynomials
m
α
i
(
x
)
and
m
α
2
i
(
x
)
have the same roots. This remark enables us to
simplify the writing of generator polynomial
g
(
x
)
.
g
(
x
)=
S.C.M.
(
m
α
(
x
)
,m
α
3
(
x
)
,
···
,m
α
2
t−
1
(
x
))
(4.21)
The degree of a minimal polynomial being lower than or equal to
m
,degree
(
n
k
)
of the generator polynomial of a primitive BCH code correcting
at least
t
errors, is therefore lower than or equal to
mt
. Indeed,
g
(
x
)
is at
most equal to the product of
t
polynomials of degree lower than or equal
to
m
.
The parameters of a primitive BCH code constructed over a Galois field
F
q
with a constructed distance
d
=2
t
+1
are therefore the following:
−
n
=2
m
2
m
−
1;
k
≥
−
1
−
mt
;
d
min
≥
2
t
+1
When
t
=1
a primitive BCH code is a Hamming code. The generator
polynomial of a Hamming code, equal to
m
α
(
x
)
, is therefore a primitive
polynomial.
Example 4.9
Let us determine the generator polynomial of a BCH code having param-
eters
m
=4
and
n
=15
,
t
=2
and
l
=1
. To do this, we will use a Galois
field with
q
=2
4
elements built from a primitive polynomial of degree
m
=4(
α
4
+
α
+1)
. The elements of this field are given in the appendix.
We must first determine the minimal polynomials
m
α
(
x
)
and
m
α
3
(
x
)
as-
sociated with elements
α
and
α
3
respectively of field
F
16
.
We have seen in the appendix that if
α
is a root of polynomial
m
α
(
x
)
then
α
2
,α
4
,α
8
are also roots of this polynomial (raising
α
to the powers of 16,
32 etc. gives, modulo
α
4
+
α
+1
,elements
α, α
2
,α
4
,α
8
). We can therefore
write:
m
α
(
x
)=(
x
+
α
)(
x
+
α
2
)(
x
+
α
4
)(
x
+
α
8
)
Developing the expression of
m
α
(
x
)
we obtain:
m
α
(
x
)=[
x
2
+
x
(
α
2
+
α
)+
α
3
][
x
2
+
x
(
α
8
+
α
4
)+
α
12
]
Using the binary representations of the elements of field
F
16
,wecanshow
that
α
2
+
α
=
α
5
and that
α
4
+
α
8
=
α
5
(we recall that the binary additions
