Finite fields

A field is an algebraic structure that lets you do everything you’re used to: you can add and multiply elements, and addition and multiplication have the usual properties you’d expect. More formally, the elements of a field form an Abelian (commutative) group with respect to addition, the non-zero elements form an Abelian group with respect to multiplication, and multiplication distributes over addition.

The rational numbers are a field. So are the real numbers and complex numbers. But it may be surprising that there are finite fields. If p is a prime, then the integers mod p form a group. For example, the integers mod 7 are the numbers 0 through 6 with addition and multiplication defined as usual, except you take the remainder by 7.

All finite fields have pn elements where p is prime and n is an integer at least 1. Conversely, for every number of the form pn there is a field that size. Furthermore, all groups of a given size are isomorphic. The field with pn elements is sometimes called the Galois field with that many elements, written GF(pn).

The Galois fields of order GF(p) are simply the integers mod p. For n > 1, the elements of GF(pn) are polynomials in n-1 variables with coefficients coming from GF(p). You add polynomials as you’d expect, but multiplication is a little different. You pick an irreducible polynomial g(x) of degree n and define multiplication in GF(pn) to be the ordinary polynomial product except you take the remainder after dividing by g(x). If you chose a different irreducible polynomial g(x) you’ll get a different definition of multiplication and hence a different field, but all such fields will be isomorphic.

Finite fields arise in applications, such as coding theory. Reed -Solomon codes, for example, are defined in terms of finite fields. Finite fields also arise in cryptography, for example in elliptic curves over finite fields. In many applications, p = 2.

Finite fields cannot be algebraically complete. In that sense you can’t have a finite analog of the complex numbers.

Example

Let’s look at GF(23), the field with 8 elements, i.e. 3-bit numbers. We choose g(x) = x³ + x + 1 as our irreducible polynomial.

The number 3 (11two) corresponds to the polynomial x + 1. The number 5 (101two) corresponds to x² + 1. The sum of 3 and 5 in this field corresponds to x² + x, which correspond to 6. (The constant terms cancel out because 1 + 1 = 0 mod 2.)

To compute the product of 5 and 6 in this field, we multiply (x² + 1)(x² + x). When we divide by x³ + x + 1, working mod 2, we get a remainder of x + 1, which corresponds to 3. So in this field, 5 times 6 equals 3.

Related posts