Page 34 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 17

1.3 Finite Fields

1.3.1 Basic Properties
A finite field is a field F which contains a finite number of elements.
The order of a finite field F is the number of elements in F.

Definition 1.21 Let p be a prime, F = Z , and f (x) an irreducible
p
polynomial of degree n over Z . The corresponding field F[x]/f (x)
p
n
contains q = p elements and is called either F or GF (q) (Galois field ).
q
Two fields are isomorphic if they have the same structure,
although the representation of their elements may be different. It can
n
be demonstrated that any finite field contains q = p elements, for
some prime p and some positive integer n, and is isomorphic to F
q
(whatever the irreducible polynomial f (x) of degree n over Z ). In
p
particular, if n = 1, then the corresponding field F is isomorphic to Z .
p p
The finite field F can henceforth be identified with Z .
p p
n
If F is a finite field of order q = p , with p a prime, then the
q
characteristic of F is p. Furthermore, F contains a copy of Z as a
q q p
subfield. Therefore, F can be considered as an extension field of Z of
q p
degree n.
The set of zero-degree polynomials (the constants) is a subfield
of F isomorphic to F . If g (x) is a zero-degree polynomial (an ele-
q p
ment of F ) then, according to the Fermat’s little theorem, ( g (x)) =
p
p
g (x). Conversely, it can be demonstrated that if a polynomial g (x)
p
satisfies the condition ( g (x)) = g (x), then g (x) is a constant.
Another interesting property of F is that the set F of nonzero
q q*
polynomials is a cyclic group. Let g (x) be a nonzero polynomial, that
is an element of F , and assume that the order of g (x) is t. According
q*
tk
k
to Properties 1.6, t divides q − 1, so that ( g (x)) q − 1 = ( g (x)) = 1 = 1.
Consider now a polynomial g (x) and define h(x) = ( g (x)) where r =
r
q − 1
p − 1
(q − 1)/(p − 1). According to the previous property, (h(x)) = ( g (x)) = 1
p
and (h(x)) = h(x), so that h(x) is a constant polynomial.
A last property, useful for performing arithmetic operations, is
p
p
p
that ( g (x) + h(x)) = ( g (x)) + (h(x)) . It is a straightforward consequence
of the fact that all the binomial coefficients (p!/(i!)(p − i )!) are multiples
of p, except for i = 0 or p.
To summarize:
Properties 1.8 (some useful properties of finite fields )
1. The set of zero-degree polynomials in F is a subfield of F
q q
isomorphic to F .
p
2. Given g (x) in F such that ( g (x)) = g (x), then g (x) ∈ F .
p
q p
3. The set of nonzero polynomials of F is a cyclic group denoted
q
by F .
q*
q
4. Given g (x) in F , then ( g (x)) = g (x) (Fermat’s little theorem ).
q