Home

An introduction to finite fields

A finite field is a particular type of mathematical field in which there is a finite number of elements and for which there is some set of defined operations that operate over the field that return results back in that field. The field must have some definition of addition, subtraction, multiplication, and division; though the meaning of those operations is up to the designer of the field so long as the operations meet the properties required of them.

It's important to understand that the design of a finite field does not have to use conventional precepts of mathematics - the elements may not be numbers, or numbers may be used but not with their usual meaning; addition may be represented using the '+' sign, but that does not necessarily mean that standard 2 + 2 = 4 addition is in use.

Properties of a finite field

A finite field is a system of elements and operations on those elements that meet the following definitions:

• The number of distinct elements in the field is finite.
• The operations of addition, subtraction, multiplication, and division have some definition in the field.
• The field addition and multiplication operations are closed - the result of a these operation over elements in the field returns another element in the field.

The field also requires the some basic properties that are typical of algebraic systems, for instance:

• Addition and multiplication support associativity and commutativity.
• Addition and multiplication each have an identity element - some element I that when applied to another element x in the field, the result is unchanged from x.

A finite field may not have an arbitrary number of elements - the size of the field is constrained to be of the form p^k, where p is a prime number, and k is an integer equal to or greater than 1. A field of this form is often identified as GF(p^k); for example, GF(2^8) or alternatively GF(256); both are ultimately identical means of identifying the same field size.

One simple finite field is where the size of the field is a prime number - this would be known as a prime field. An easy definition for a prime field is to define the multiplication and addition operations simply as integer arithmetic, modulo p.

For instance, consider a field GF(7), with the elements {0, 1, 2, 3, 4, 5, 6} with integer addition and multiplication, modulo 7. The operation 3 + 5 in the field would be computed as (3 + 5) mod 7 --> 8 mod 7 --> 1. Multiplication would be computed as (4 * 6) mod 7 --> 24 mod 7 --> 3. The properties of modulus are sufficient to keep the field finite and closed, and the properties of standard integer addition and multiplication are sufficient to satisfy the algebraic requirements of the field.

A more useful field for computer science is a field of the form GF(2^k), handy because it neatly works with bits.

A problem arises with constructing such a field, however - our go-to construction using multiplication modulus p^k no longer works; integer multiplication modulus p^k does not form a ring of integers, and thus the properties of the field do not hold like they do when simply using modulus p.

We can however, easily define addition. We can consider the elements of the field in their binary representation, and then apply bitwise-XOR to the bits of the elements. For instance, adding 2 + 7 in GF(16) with XOR addition would be 10 XOR 111 == 101 --> 5.

There is a means to define multiplication for such a field, but it's a little complicated. The summary of the technique is that we define multiplication using polynomials over the prime field equipped with modulus arithmetic, and define multiplication by way of logarithms.

First, polynomials. If we have elements in GF(2^k), we can treat those elements as polynomials over the field GF(2) - that is, the coefficients of these polynomials are the elements from GF(2). For instance, if we have the element 14 in GF(2^4), 14 would have binary representation 1110. Treated as a polynomial over GF(2), it would be the polynomial 1x^3 + 1x^2 + 1x^1 + 0x^0. 14 in GF(2^4) is x^3 + x^2 + x in GF(2).