Cryptography Reference
In-Depth Information
Appendix
Notions about Galois fields
and minimal polynomials
Definition
A Galois field with
q
=2
m
elements denoted
F
q
,where
m
is a positive integer is
defined as a polynomial extension of the field with two elements
(0
,
1)
denoted
F
2
. The polynomial
ϕ
(
x
)
used to build field
F
q
must be
•
irreducible, that is, non factorizable in
F
2
(in other words, 0 and 1 are not
roots of
ϕ
(
x
)
),
•
of degree
m
,
•
andwithcoecientsin
F
2
.
The elements of a Galois field
F
q
are defined modulo
ϕ
(
x
)
and thus, each element
of this field can be represented by a polynomial with degree at most equal to
(
m
−
1)
and with coecients in
F
2
.
Example 1
Consider an irreducible polynomial
ϕ
(
x
)
in the field
F
2
of degree
m
=2
.
ϕ
(
x
)=
x
2
+
x
+1
This polynomial enables a Galois field to be built with 4 elements. The elements
of this field
F
4
are of the form:
aα
+
b
where
a, b
∈
F
2
that is:
F
4
:
{
0
,
1
,α,α
+1
}
