Cryptography Reference
In-Depth Information
Minimal polynomial with coecients in
F
q
associ-
ated with an element in a Galois field
F
q
The minimal polynomial
m
β
(
x
)
, with coecients in the Galois field
F
q
associ-
ated with an element
β
=
α
j
(
α
a primitive element of field
F
q
) of this field, is
the lowest degree polynomial having
β
as a root.
Recalling that for a polynomial with coecients in
F
q
,wecanwrite:
[
f
(
x
)]
q
p
=
f
(
x
q
p
)
[
f
(
x
)]
q
=
f
(
x
q
)
⇒
Then if
β
is a root of polynomial
f
(
x
)
,
β
q
,β
q
2
,
···
are also roots of this polyno-
mial.
Since in field
F
q
=1
,then
β
q
p
=(
α
j
)
q
p
α
q−
1
=
α
j
=
β
and, thus, minimal
polynomial
m
β
(
x
)
is simply equal to:
m
β
(
x
)=
x
+
β
These results on minimal polynomials are used to determine the generator poly-
nomials of particular cyclic codes (BCH and Reed-Solomon).
Primitive polynomials
A polynomial with coecients in
F
2
is primitive if it is the minimal polynomial
associated with a primitive element of a Galois field. A primitive polynomial
is thus irreducible in
F
2
and consequently can be used to build a Galois field.
When a primitive polynomial is used to build a Galois field, all the elements of
the field are obtained by raising the primitive element, the root of the primitive
polynomial, to successively increasing powers. As the main primitive polynomi-
als are listed in the literature, the construction of a Galois field with
q
=2
m
elements can then be done simply by using a primitive polynomial of degree
m
.
Table 4.9 gives some primitive polynomials.
To end this introduction to Galois fields and minimal polynomials, let us
give an example of a Galois field with
q
=16
(
m
=4
) elements built from the
primitive polynomial
x
4
+
x
+1
. This field is used to build generator polynomials
of BCH and Reed-Solomon codes and to decode them. The elements of this field
are:
F
16
=
0
,
1
,α,α
2
,α
3
α
14
···
where
α
is a primitive element of
F
16
. With these 16 elements, we can also asso-
ciate a polynomial representation and a binary representation. The polynomial
representation of an element of this field is of the form:
aα
3
+
bα
2
+
cα
+
d
where
a
,
b
,
c
and
d
are binary coecients belonging to
F
2
.
