LOGO

Finite Fields

Philip J. Erdelsky

February 9, 2009

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

1. Basic Properties

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 Zp, 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 Zp, where 2 is defined as 1+1, 3 is defined as 2+1, etc.

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 Zp, and let N = p n. Consider the polynomial p(x) = x N - x. It is relatively prime to its formal derivative -1, so it has distinct roots in its splitting field.

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-1b + (p(p-1)/2!) a p-2b 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 b N = b. Then the above result becomes

(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 GF(p n).

2. Multiplicative Group is Cyclic

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 x M - 1 and x M - 1 divides x N-1 - 1. These polynomials, too, have distinct roots. Hence there are roots of x N-1 - 1 that are also roots of x M - 1 but not roots of x M/q - 1. These roots have order M.

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 1, g, g 2, ... of the generator are vectors in an n-dimensional vector space over GF(p). Hence 1, g, g 2, ... g n must be linearly dependent, i.e., g is a root of a polynomial of degree no more than n over GF(p).

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 GF(p). Since g has p n - 1 distinct powers, a simple counting argument shows that m=n.

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 x N-1 - 1, whose roots are all the nonzero elements of GF(p n), into its monic prime factors over GF(p). Since g is a root of this polynomial, it must be root of one of the factors, which must be identical to the polynomial r(x). Hence the other roots of r(x) are also elements of GF(p n).

Now let q be any divisor of N-1 which is less than N-1. Then x q - 1 divides x N-1 - 1, so when x N-1 - 1 is factored into its monic prime factors over GF(p), the prime factor r(x) must divide x q - 1 or be relatively prime to it. The former is impossible, because g is not a root of x q - 1. Hence no other root of r(x) can be a root of x q - 1, and all must be generators of GF(p n). █

3. Error Detection and Correction

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 GF(2):

0, 0, 1, 1, 0, 1, 0, 0, 0, ..., 1, 0, 0
Somewhere along the way, a single bit may be changed:
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 GF(2)[x]. Notice that in a field of characteristic 2 there is no difference between addition and subtraction.

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

m(x) = b1 x N-2 + b2 x N-3 + ... + bN-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 m(x) + s(x) + x k. The remainder will be nonzero, because r(x) and x k are relatively prime.

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 x k will be the remainder produced by dividing x j + x k by r(x). This is also nonzero, because x j + x k is also relatively prime to r(x).

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

4. Shift Register Sequences

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 x0, x1, x2, ... is generated by specifying the first n values and then using a linear recurrence formula to compute subsequent values:

xk+n = cn-1xk+n-1 + cn-2xk+n-2 + ... + c0xk, 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:

xn-1, xn-2, xn-3, ..., x0.

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 c0 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 starting values.

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

z n - cn-1z n-1 - cn-2z n-2 - ... - c1z - c0
are generators of the field GF(p n). Let them be denoted by g1, g2, ..., gn. Notice that c0 ≠ 0, because none of the generators is zero.

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 x0 = 1, x1 = gr, x2 = gr 2, x3 = gr 3, etc. Then

gr n - cn-1gr n-1 - cn-2gr n-2 - ... - c1gr - c0 = 0,
gr n = cn-1gr n-1 + cn-2gr n-2 + ... + c1gr + c0,
gr k+n = cn-1gr k+n-1 + cn-2gr k+n-2 + ... + c1gr k+1 + c0gr k.

However, such a sequence would not be generated because the initial values gr n-1, gr n-1, ..., gr , 1 would not all be in the base field GF(p).

Suppose we take a linear combination of powers of generators:

xk = d1g1 k + d2g2 k + ... + dngn k.

The recurrence formula is still satisfied. We must choose the coefficients d1, d2, ..., dn so that the initial conditions are satisfied:

d1 + d2 + ... + dn = x0,
d1g1 + d2g2 + ... + dngn = x1,
d1g1 2 + d2g2 2 + ... + dngn 2 = x2,
***
d1g1 n-1 + d2g2 n-1 + ... + dngn n-1 = xn-1.

The matrix of this system is the transpose of a square Vandermonde matrix, and it is nonsingular because g1, g2, ..., gn are all distinct. Hence a unique solution exists, and at least one of the coefficients d1, d2, ..., dn is nonzero.

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

d1g1 k + d2g2 k + ... + dngn k = d1 + d2 + ... + dn,
d1g1 k+1 + d2g2 k+1 + ... + dngn k+1 = d1g1 + d2g2 + ... + dngn,
d1g1 k+2 + d2g2 k+2 + ... + dngn k+2 = d1g1 2 + d2g2 2 + ... + dngn 2,
***
d1g1 k+n-1 + d2g2 k+n-1 + ... + dngn k+n-1 = d1g1 n-1 + d2g2 n-1 + ... + dngn n-1.

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

d1(g1 k-1) + d2(g2 k-1) + ... + dn(gn k-1) = 0,
d1g1(g1 k-1) + d2g2(g2 k-1) + ... + dngn(gn k-1) = 0,
d1g1 2(g1 k-1) + d2g2 2(g2 k-1) + ... + dngn 2(gn k-1) = 0,
***
d1g1 n-1(g1 k-1) + d2g2 n-1(g2 k-1) + ... + dngn n-1(gn k-1) = 0.

This can be interpreted as the matrix equation Ax = 0, where xi = di(gi k-1) and A is the nonsingular matrix used previously. Hence x = 0; i.e., di(gi k-1) = 0 for all 1 ≤ i ≤ n. Since at least one di is nonzero, the corresponding gi k-1 is zero. Since gi is a generator, the smallest positive value of k for which this can happen is p n-1.

Links