## Finite Fields## Philip J. Erdelsky## February 9, 2009 |

Please e-mail comments, corrections and additions to the webmaster at pje@efgh.com.

A finite field (also called a __Galois field__) is a field with a finite
number of elements. Finite fields have many applications, especially in
cryptography and communications.

Finite fields are characterized by the following theorem.

**Theorem 1.1** *For every prime number p and every positive integer
n, there is one and only one field with p ^{ n} elements,
it is the minimal splitting field of x^{ p n} - x over
Z_{p},
and these are the only finite fields.*

*Proof.* We first prove that every finite field has
*p ^{ n}* elements.

Obviously, a finite field must have a finite characteristic *p*.
The field elements *{0, 1, 2, ..., p-1}* are a subfield *G* isomorphic
to *Z _{p}*, where

The field itself constitutes a vector space over *G*, which obviously
has a finite dimension *n*. Since each field element can be expressed
uniquely as a linear combination of *n* basis vectors, the total number
of field elements is *p ^{ n}*.

We now prove that there is a finite field with *p ^{ n}*
elements.

Start with the field *Z _{p}*, and let

The splitting field, like the base field, has characteristic *p*.
If *a* and *b* are any field elements, then by the binomial
theorem

(a+b)^{ p}= a^{ p}+ p a^{ p-1}b + (p(p-1)/2!) a^{ p-2}b^{ 2}+ ... + b^{ p}.

Because every binomial coefficient except the first and last is divisible
by *p*, this reduces to

(a+b)^{ p}= a^{ p}+ b^{ p}.

Then

(a+b)^{ p}^{ 2}= ((a+b)^{ p})^{ p}= (a^{ p}+ b^{ p})^{ p}= a^{ p}^{ 2}+ b^{ p}^{ 2}.

Repeated application of this result yields

(a+b)^{ N}= a^{ N}+ b^{ N}.

If *a* and *b* are roots of *p(x)*, then
*a ^{ N} = a* and

(a+b)^{ N}= a + b.

Therefore, the sum of two roots of *p(x)* is also a
root of *p(x)*.

Similarly, it can be shown that the product of two roots of
*p(x)* is also a root of *p(x)*.

Hence the *N* roots of *p(x)* constitute the entire
splitting field, which is unique up to isomorphism.
█

The Galois field with *p ^{ n}* elements is often
written as

The nonzero elements of a field constitute a commutative group under multiplication. For finite fields, this group has a particularly simple structure.

First, we need a basic property of polynomials.

**Lemma 2.1** *If m divides n, then x ^{ m} - 1 divides
x^{ n} - 1.*

*Proof.* Let *d = n/m*. Then *n = dm* and
the required factorization is as follows:

█x^{ dm}- 1 = (x^{ m}- 1) (x^{ (d-1)m}+ x^{ (d-2)m}+ ... + x^{ m}+ 1).

**Theorem 2.2** *The group of nonzero elements of a finite field
under multiplication is cyclic.*

*Proof.*
Let *N* be the number of elements in the field. Then the nonzero
elements are the roots of *x ^{ N-1} - 1*,
which are all distinct.

If *N = 2* the result is obvious.

In other cases, let *q* be a prime factor of *N-1* and
let *m* be the number of times it occurs in the prime factorization
of *N-1*. For convenience in notation let *M = q ^{ m}*.

By the lemma, *x ^{ M/q} - 1* divides

Now take one such root for each prime factor of *N-1*. By Theorem
4.1 of Groups their product has order *N-1*. This shows that
the group is cyclic.
█

An element *g* of *GF(N)* with
order *N-1* in the multiplicative group is called
a __generator__ or a __primitive element__ of the field.

**Theorem 2.3.** *Every generator of GF(p ^{ n})
is the root of a unique monic irreducible polynomial of degree n
with coefficients in GF(p), and the other roots of this polynomial
are also generators.*

*Proof.*
Let *g* be any generator of
*GF(p ^{ n})*. The powers

Let *r(x)* be a monic polynomial of lowest degree
over
*GF(p)* which
has *g* as a root. Let the degree be
*m*. Then the identity *r(g) = 0*
can be used to express any power of *g* as
a linear combination of
*1, g, g ^{ 2}, ... g^{ m-1}*
with coefficients in

The polynomial *r(x)* must be irreducible over
*GF(p)*, since otherwise *g*
would be a root of at least one of its factors.

Now consider two such polynomials. They have a common factor
*x - g*, so they cannot be relatively prime
over either *GF(p)* or
*GF(p ^{ n})*.
This can happen only if they are identical.

Now let *N = p ^{ n}*
and factor

Now let *q* be any divisor of
*N-1* which is less than *N-1*.
Then *x ^{ q} - 1*
divides

There is an interesting application of finite field theory to communications.
Usually, the field is of characteristic *2*,
because arithmetic on *GF(2)* is
easily implemented with digital hardware.

Let *N = 2 ^{ n}*
Suppose a message is somehow encoded in a stream of bits, i.e, as
elements of

Somewhere along the way, a single bit may be changed:0, 0, 1, 1, 0, 1, 0, 0, 0, ..., 1, 0, 0

0, 0, 1, 1, 0, 0, 0, 0, 0, ..., 1, 0, 0

We want to send additional bits, calculated so we can determine whether a bit was changed (error detection) and if so, which bit (error correction). The changed bit may be one of the additional bits.

We can do this by the use of the finite field *GF(N)*,
where *N = 2 ^{ n}*, and modular arithmetic
on the polynomial ring

Encode the message in *N-n-1* bits, and imagine
them to be the coefficients of a polynomial over
*GF(2)*:

m(x) = b_{1}x^{ N-2}+ b_{2}x^{ N-3}+ ... + b_{N-n-1}x^{ n}

Now let *g* be a generator of *GF(N)*
which is a root of the monic irreducible polynomial *r(x)* over
*GF(2)*.

Now divide *m(x)* by *r(x)*
to obtain the remainder *s(x)*.

Transmit the coefficients of the sum *m(x) + s(x)*.
Notice that *s(x)* fits comfortably into the unoccupied
portion of *m(x)*.

When the coefficients of *m(x) + s(x)* are received,
divide the corresponding polynomial by *r(x)* and
obtain the remainder *t(x)*.

If the coefficients were received accurately, the remainder will be zero.

If a single bit (the coefficient of *x ^{ k}*)
has been changed, then the polynomial
will be

We can identify the changed bit if different bit changes produce different
remainders. The difference of the remainders produced by errors in
*x ^{ j}* and

In an actual implementation, minor changes may be made to improve computational efficiency.

In many applications, we need to create a stream of more or less random
numbers. One way to do this is with a __shift register sequence__.

The sequence *x _{0}, x_{1},
x_{2}, ...* is generated by specifying the first

x_{k+n}= c_{n-1}x_{k+n-1}+ c_{n-2}x_{k+n-2}+ ... + c_{0}x_{k}, k = 0, 1, 2, 3, ...

Usually, the sequence values and the coefficients are taken from
the field *GF(2)*, but our treatment will
apply equally well if they are taken from
*GF(p)* for any prime *p*.

The computations are usually carried out by first loading
the initial values into an *n*-value register:

x_{n-1}, x_{n-2}, x_{n-3}, ..., x_{0}.

At each step, the values are shifted to the right. The value at the
right end is discarded, and the new value for the left end is computed
with the recurrence formula. When all values are single bits from
*GF(2)*, the computations are quite simple.

Since there are only finitely many combinations of
values, the device will eventually repeat. We want to maximize the
number of steps taken before this happens. The total number of
combinations is *p ^{ n}*, but one of
them, in which all values are zeros, is prohibited because the
recurrence formula wouldn't change it.

If the coefficient *c _{0}* is nonzero,
as it is in virtually all applications, then the sequence can also
be run backward. This implies that when it repeats, it first
returns to the

We can get the maximum number *p ^{ n}-1* of steps between repeats if we choose
the coefficients so the roots of the polynomial

are generators of the fieldz^{ n}- c_{n-1}z^{ n-1}- c_{n-2}z^{ n-2}- ... - c_{1}z - c_{0}

The starting values don't matter, as long as they are not all zeros.

To prove this, we first note that the powers of each generator obey
the recurrence formula. For example, suppose that
*
x _{0} = 1,
x_{1} = g_{r},
x_{2} = g_{r}^{ 2},
x_{3} = g_{r}^{ 3}*, etc. Then

g_{r}^{ n}- c_{n-1}g_{r}^{ n-1}- c_{n-2}g_{r}^{ n-2}- ... - c_{1}g_{r}- c_{0}= 0,

g_{r}^{ n}= c_{n-1}g_{r}^{ n-1}+ c_{n-2}g_{r}^{ n-2}+ ... + c_{1}g_{r}+ c_{0},

g_{r}^{ k+n}= c_{n-1}g_{r}^{ k+n-1}+ c_{n-2}g_{r}^{ k+n-2}+ ... + c_{1}g_{r}^{ k+1}+ c_{0}g_{r}^{ k}.

However, such a sequence would not be generated because the initial
values *g _{r}^{ n-1},
g_{r}^{ n-1}, ..., g_{r} , 1*
would not all be in the base field

Suppose we take a linear combination of powers of generators:

x_{k}= d_{1}g_{1}^{ k}+ d_{2}g_{2}^{ k}+ ... + d_{n}g_{n}^{ k}.

The recurrence formula is still satisfied. We must choose the
coefficients *d _{1}, d_{2},
..., d_{n}* so that the initial conditions are
satisfied:

d_{1}+ d_{2}+ ... + d_{n}= x_{0},

d_{1}g_{1}+ d_{2}g_{2}+ ... + d_{n}g_{n}= x_{1},

d_{1}g_{1}^{ 2}+ d_{2}g_{2}^{ 2}+ ... + d_{n}g_{n}^{ 2}= x_{2},

***

d_{1}g_{1}^{ n-1}+ d_{2}g_{2}^{ n-1}+ ... + d_{n}g_{n}^{ n-1}= x_{n-1}.

The matrix of this system is the transpose of a square Vandermonde
matrix, and it is nonsingular because *g _{1}, g_{2},
..., g_{n}* are all distinct. Hence a unique solution
exists, and at least one of the coefficients

The sequence starts to repeat when it returns to its original configuration; i.e., for the smallest positive value of k for which:

d_{1}g_{1}^{ k}+ d_{2}g_{2}^{ k}+ ... + d_{n}g_{n}^{ k}= d_{1}+ d_{2}+ ... + d_{n},

d_{1}g_{1}^{ k+1}+ d_{2}g_{2}^{ k+1}+ ... + d_{n}g_{n}^{ k+1}= d_{1}g_{1}+ d_{2}g_{2}+ ... + d_{n}g_{n},

d_{1}g_{1}^{ k+2}+ d_{2}g_{2}^{ k+2}+ ... + d_{n}g_{n}^{ k+2}= d_{1}g_{1}^{ 2}+ d_{2}g_{2}^{ 2}+ ... + d_{n}g_{n}^{ 2},

***

d_{1}g_{1}^{ k+n-1}+ d_{2}g_{2}^{ k+n-1}+ ... + d_{n}g_{n}^{ k+n-1}= d_{1}g_{1}^{ n-1}+ d_{2}g_{2}^{ n-1}+ ... + d_{n}g_{n}^{ n-1}.

When all terms are moved to the left side and combined, this becomes:

d_{1}(g_{1}^{ k}-1) + d_{2}(g_{2}^{ k}-1) + ... + d_{n}(g_{n}^{ k}-1) = 0,

d_{1}g_{1}(g_{1}^{ k}-1) + d_{2}g_{2}(g_{2}^{ k}-1) + ... + d_{n}g_{n}(g_{n}^{ k}-1) = 0,

d_{1}g_{1}^{ 2}(g_{1}^{ k}-1) + d_{2}g_{2}^{ 2}(g_{2}^{ k}-1) + ... + d_{n}g_{n}^{ 2}(g_{n}^{ k}-1) = 0,

***

d_{1}g_{1}^{ n-1}(g_{1}^{ k}-1) + d_{2}g_{2}^{ n-1}(g_{2}^{ k}-1) + ... + d_{n}g_{n}^{ n-1}(g_{n}^{ k}-1) = 0.

This can be interpreted as the matrix equation
* Ax = 0*, where