Finite field


In mathematics, a finite field or Galois field is a field that has a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are the integers mod when is a prime number.
The order of a finite field is its number of elements, which is either a prime number or a prime power. For every prime number and every positive integer there are fields of order. All finite fields of a given order are isomorphic.
Finite fields are fundamental in a number of areas of mathematics and computer science, including number theory, algebraic geometry, Galois theory, finite geometry, cryptography and coding theory.

Properties

A finite field is a field that is a finite set; this means that it has a finite number of elements on which multiplication, addition, subtraction and division are defined and satisfy the field axioms.
The number of elements of a finite field is called its order or, sometimes, its size. A finite field of order exists if and only if is a prime power . In a field of order, adding copies of any element always results in zero; that is, the characteristic of the field is.
For, all fields of order are isomorphic. Moreover, a field cannot contain two different finite subfields with the same order. One may therefore identify all finite fields with the same order, and they are unambiguously denoted, or, where the letters GF stand for "Galois field".
In a finite field of order, the polynomial has all elements of the finite field as roots. The non-zero elements of a finite field form a multiplicative group. This group is cyclic, so all non-zero elements can be expressed as powers of a single element called a primitive element of the field.
The simplest examples of finite fields are the fields of prime order: for each prime number, the prime field of order may be constructed as the integers modulo,.
The elements of the prime field of order may be represented by integers in the range. The sum, the difference and the product are the remainder of the division by of the result of the corresponding integer operation. The multiplicative inverse of an element may be computed by using the extended Euclidean algorithm.
Let be a finite field. For any element in and any integer, denote by the sum of copies of. The least positive such that is the characteristic of the field. This allows defining a multiplication of an element of by an element of by choosing an integer representative for. This multiplication makes into a -vector space. It follows that the number of elements of is for some integer.
The identity
is true in a field of characteristic. This follows from the binomial theorem, as each binomial coefficient of the expansion of, except the first and the last, is a multiple of.
By Fermat's little theorem, if is a prime number and is in the field then. This implies the equality
for polynomials over. More generally, every element in satisfies the polynomial equation.
Any finite field extension of a finite field is separable and simple. That is, if is a finite field and is a subfield of, then is obtained from by adjoining a single element whose minimal polynomial is separable. To use a piece of jargon, finite fields are perfect.
Finite fields are quasi-algebraically closed: every degree homogeneous polynomial in variables over a finite field with has a nontrivial zero. This was a conjecture of Artin and Dickson, and was proved by Chevalley; see Chevalley–Warning theorem.

Existence and uniqueness

Let be a prime power, and be the splitting field of the polynomial
over the prime field. This means that is a finite field of lowest order, in which has distinct roots. The [|above identity] shows that the sum and the product of two roots of are roots of, as well as the multiplicative inverse of a root of. In other words, the roots of form a field of order, which is equal to by the minimality of the splitting field.
The uniqueness up to isomorphism of splitting fields implies thus that all fields of order are isomorphic. Also, if a field has a field of order as a subfield, its elements are the roots of, and cannot contain another subfield of order.
In summary, we have the following classification theorem first proved in 1893 by E. H. Moore:

The order of a finite field is a prime power. For every prime power there are fields of order, and they are all isomorphic. In these fields, every element satisfies
and the polynomial factors as

It follows that contains a subfield isomorphic to if and only if is a divisor of ; in that case, this subfield is unique. In fact, the polynomial divides if and only if is a divisor of.

Explicit construction

Non-prime fields

Given a prime power with prime and, the field may be explicitly constructed in the following way. One first chooses an irreducible polynomial in of degree . Then the quotient ring
of the polynomial ring by the principal ideal generated by is a field of order.
More explicitly, the elements of are the polynomials over whose degree is strictly less than. The addition and the subtraction are those of polynomials over. The product of two elements is the remainder of the Euclidean division by of the product in.
The multiplicative inverse of a non-zero element may be computed with the extended Euclidean algorithm; see .
However, with this representation, elements of may be difficult to distinguish from the corresponding polynomials. Therefore, it is common to give a name, commonly to the element of that corresponds to the polynomial. So, the elements of become polynomials in, where, and, when one encounters a polynomial in of degree greater or equal to , one knows that one has to use the relation to reduce its degree.
Except in the construction of, there are several possible choices for, which produce isomorphic results. To simplify the Euclidean division, one commonly chooses for a polynomial of the form
which make the needed Euclidean divisions very efficient. However, for some fields, typically in characteristic, irreducible polynomials of the form may not exist. In characteristic, if the polynomial is reducible, it is recommended to choose with the lowest possible that makes the polynomial irreducible. If all these trinomials are reducible, one chooses "pentanomials", as polynomials of degree greater than, with an even number of terms, are never irreducible in characteristic, having as a root.
A possible choice for such a polynomial is given by Conway polynomials. They ensure a certain compatibility between the representation of a field and the representations of its subfields.
In the next sections, we will show how the general construction method outlined above works for small finite fields.

Field with four elements

The smallest non-prime field is the field with four elements, which is commonly denoted or It consists of the four elements such that,,, and, for every, the other operation results being easily deduced from the distributive law. See below for the complete operation tables.
This may be deduced as follows from the results of the preceding section.
Over, there is only one irreducible polynomial of degree :
Therefore, for the construction of the preceding section must involve this polynomial, and
Let denote a root of this polynomial in. This implies that
and that and are the elements of that are not in. The tables of the operations in result from this, and are as follows:

A table for subtraction is not given, because subtraction is identical to addition, as is the case for every field of characteristic 2. To divide, multiply by the reciprocal:. As in any field, division by zero is undefined. From the tables, it can be seen that the additive structure of is isomorphic to the Klein four-group, while the non-zero multiplicative structure is isomorphic to the group.
The map
is the non-trivial field automorphism, called the [|Frobenius automorphism], which sends into the second root of the above-mentioned irreducible polynomial.

GF(''p''2) for an odd prime ''p''

For applying the [|above general construction] of finite fields in the case of, one has to find an irreducible polynomial of degree 2. For, this has been done in the preceding section. If is an odd prime, there are always irreducible polynomials of the form, with in.
More precisely, the polynomial is irreducible over if and only if is a quadratic non-residue modulo . There are quadratic non-residues modulo. For example, is a quadratic non-residue for, and is a quadratic non-residue for. If, that is, one may choose as a quadratic non-residue, which allows us to have a very simple irreducible polynomial.
Having chosen a quadratic non-residue, let be a symbolic square root of, that is, a symbol that has the property, in the same way that the complex number is a symbolic square root of. Then, the elements of are all the linear expressions
with and in. The operations on are defined as follows :

GF(8) and GF(27)

The polynomial
is irreducible over and, that is, it is irreducible modulo and . It follows that the elements of and may be represented by expressions
where are elements of or , and is a symbol such that
The addition, additive inverse and multiplication on and may thus be defined as follows; in following formulas, the operations between elements of or, represented by Latin letters, are the operations in or, respectively:

GF(16)

The polynomial
is irreducible over, that is, it is irreducible modulo. It follows that the elements of may be represented by expressions
where are either or , and is a symbol such that
. As the characteristic of is, each element is its additive inverse in. The addition and multiplication on may be defined as follows; in following formulas, the operations between elements of, represented by Latin letters are the operations in.
The field has eight primitive elements. These elements are the four roots of and their multiplicative inverses. In particular, is a primitive element, and the primitive elements are with less than and coprime with .