Main Page | See live article | Alphabetical index

Finite field

In abstract algebra, a finite field or Galois field (so named in honor of Evariste Galois) is a field that contains only finitely many elements. Finite fields are important in cryptography and coding theory. The finite fields are completely known, as will be described below.

Table of contents
1 The complete list
2 Examples
3 Properties and facts
4 Applications

The complete list

Since every field of characteristic 0 contains the rationals and is therefore infinite, all finite fields have prime characteristic.

If p is a prime, the integers modulo p form a field with p elements, denoted by Zp, Fp or GF(p). Every other field with p elements is isomorphic to this one.

If q = pn is a prime power, then there exists up to isomorphism exactly one field with q elements, written as Fq or GF(q). It can be constructed as follows: find an irreducible polynomial f(T) of degree n with coefficients in GF(p), then define GF(q) = GF(p)[T] / <f(T)>. Here, GF(p)[T] denotes the ring of all polynomials with coefficients in GF(p), and the quotient is meant in the sense of factor rings - the set of polynomials with coefficients in GF(p) on division by f(T). The polynomial f(T) can be found by factoring the polynomial T q-T over GF(p). The field GF(q) contains GF(p) as a subfield.

There are no other finite fields.

Examples

The polynomial f(T) = T 2 + T + 1 is irreducible over GF(2), and GF(4)=GF(2)/<T2+T+1> can therefore be written as the set {0, 1, t, t+1} where the multiplication is defined (modularly) by t2 + t + 1 = 0. For example, to determine t3, note that t(t2 + t + 1) = 0; so t3 + t2 + t = 0, and thus t3 + t2 + t + 1 = 1, so t3 = 1. Similarly, since the characteristic of the field is 2 - coefficients are in GF(2), we can calculate powers of t in this instance can be calculated by noting first that t2+t+1=0, and then t2=t+1. Then t3 = '\'t(t2) = t(t+1) = t2+t = (t+1)+t'' = 1 as before.

In order to find the multiplicative inverse of t in this field, we have to find a polynomial p(T) such that T * p(T) = 1 modulo T 2 + T + 1. The polynomial p(T) = T + 1 works, and hence 1/t = t + 1. Note that the field GF(4) is completely unrelated to the ring Z4 of integers modulo 4.

To construct the field GF(27), we start with the irreducible polynomial T 3 + T 2 + T - 1 over GF(3). We then have GF(27) = {at2 + bt + c : a, b, c in GF(3)}, where the multiplication is defined by t 3 + t 2 + t - 1 = 0, or working from the rearrangement of the above in isolating the t3 term.

Properties and facts

If F is a finite field with q = pn elements (where p is prime), then xq = x for all x in F. Furthermore, the Frobenius homomorphism f : F -> F defined by f(x) = xp is bijective, and is therefore an automorphism. The Frobenius homomorphism has order n, and the cyclic group it generates is the full group of automorphisms of the field.

The field GF(pm) contains a copy of GF(pn) if and only if n divides m. The reason for this is that there exist irreducible polynomials of every degree over GF(pn).

If we actually construct our finite fields in such a fashion that GF(pn) is contained in GF(pm) whenever n divides m, then we can form the union of all these fields. This union is also a field, albeit an infinite one. It is the algebraic closure of each of the fields GF(pn).

Applications

The multiplicative group of every finite field is cyclic, a special case of a theorem mentioned in the article about fields. This means that if F is a finite field with q elements, then there always exists an element x in F such that F = { 0, 1, x, x2, ..., xq-2 }.

The element x is not unique. If we fix one, then for any non-zero element a in Fq, there is a unique integer n in {0, ..., q - 2} such that a = xn. The value of n for a given a is called the discrete log of a (in the given field, to base x). In practice, although calculating xn is relatively trivial given n, finding n for a given a is (under current theories) a computationally difficult process, and so has many applications in cryptography.

Finite fields also find applications in coding theory: many codes are constructed as subspacess of vector spaces over finite fields.\n