In mathematics, a finite field or Galois field is a field that contains 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
given by the integers mod n when n is a prime number.
The number of elements of a finite field is called its order. A finite field of
order q exists if and only if the order q is a prime power pk. All fields of a
given order are isomorphic. In a field of order pk, adding p copies of any
element always results in zero; that is, the characteristic of the field is p.
In a finite field of order q, the polynomial Xq − X has all q 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
A field has, by definition, a commutative multiplication operation. A
more general algebraic structure that satisfies all the other axioms of a
field but isn't required to have a commutative multiplication is called a
division ring. A finite division ring is a finite field by Wedderburn's little
theorem. This result shows that the finiteness condition in the definition
of a finite field can have algebraic consequences.
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.
Finite fields appear in the following chain of class inclusions:
Commutative rings ⊃ integral domains ⊃ integrally closed domains ⊃ unique
factorization domains ⊃ principal ideal domains ⊃ Euclidean domains ⊃ fields ⊃
finite fields Definitions, first examples, and basic
properties A finite field is a finite set on which
the four operations multiplication, addition, subtraction and division are
defined, satisfying the rules of arithmetic known as the field axioms.
The simplest examples of finite fields are the prime fields: for each prime
number p, the field GF(p) of order p is easily constructed as the integers
modulo p. The elements of a prime field may be
represented by integers in the range 0, ..., p − 1. The sum, the difference and
the product are computed by taking the remainder by p of the integer result.
The multiplicative inverse of an element may be computed by using the extended
Euclidean algorithm. Let F be a finite field. For any element
x in F and any integer n, let us denote by n⋅x the sum of n copies of x. The
least positive n such that n⋅1 = 0 must exist and is prime; it is called the
characteristic of the field. If the characteristic of F is p, the
operation makes F a GF(p)-vector space. It follows that the number of elements
of F is pn. For every prime number p and every
positive integer n, there are finite fields of order pn, and all these fields
are isomorphic. One may therefore identify all fields of order pn, which
are therefore unambiguously denoted , Fpn or GF(pn), where the letters GF
stand for "Galois field". The identity
is true in a field of characteristic p.. For every element x in the prime field
GF(p), one has xp = x by applying the above identity to x and 1, where x
successively takes the values 1, 2, ..., p − 1 modulo p.) This implies the
equality for polynomials over GF(p). More
generally, every element in GF(pn) satisfies the polynomial equation xpn −
x = 0. Any finite field extension of a finite
field is separable and simple. That is, if E is a finite field and F is a
subfield of E, then E is obtained from F by adjoining a single element whose
minimal polynomial is separable. To use a jargon, finite fields are perfect.
Existence and uniqueness Let q = pn be a prime power, and F be
the splitting field of the polynomial over the prime field GF(p). This means
that F is a finite field of lowest order, in which P has q distinct roots.
Above identity shows that the sum and the product of two roots of P are roots
of P, as well as the multiplicative inverse of a root of P. In other word,
the roots of P form a field of order q, which is equal to F by the minimality of
the splitting field. The uniqueness up to isomorphism of
splitting fields implies thus that all fields of order q are isomorphic.
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 q there are fields of order q, and they are all
isomorphic. In these fields, every element satisfies
and the polynomial factors as It follows that GF(pn) contains a
subfield isomorphic to GF(pm) if and only if m is a divisor of n; in that
case, this subfield is unique. In fact, the polynomial divides if and only if
m is a divisor of n. Explicit construction of finite fields
= Non-prime fields= Given a prime power q = pn with p prime
and n > 1, the field GF(q) may be explicitly constructed in the following
way. One chooses first an irreducible polynomial P in GF(p)[X] of degree n.
Then the quotient ring of the polynomial ring GF(p)[X] by the
ideal generated by P is a field of order q.
More explicitly, the elements of GF(q) are the polynomials over GF(p) whose
degree is strictly less than n. The addition and the subtraction are those
of polynomials over GF(p). The product of two elements is the remainder of the
Euclidean division by P of the product in GF(p)[X]. The multiplicative inverse
of a non-zero element may be computed with the extended Euclidean algorithm;
see Extended Euclidean algorithm § Simple algebraic field extensions.
Except in the construction of GF(4), there are several possible choices for
P, which produce isomorphic results. To simplify the Euclidean division, for P
one commonly chooses polynomials of the form
which make the needed Euclidean divisions very efficient. However, for
some fields, typically in characteristic 2, irreducible polynomials of the form
may not exist. In characteristic 2, if the polynomial Xn + X + 1 is reducible,
it is recommended to choose Xn + Xk + 1 with the lowest possible k that makes
the polynomial irreducible. If all these trinomials are reducible, one chooses
"pentanomials" Xn + Xa + Xb + Xc + 1, as polynomials of degree greater than 1,
with an even number of terms, are never irreducible in characteristic 2, having
1 as a root. In the next sections, we will show how
this general construction method works for small finite fields.
= Field with four elements= Over GF(2), there is only one
irreducible polynomial of degree 2: Therefore, for GF(4) the construction of
the preceding section must involve this polynomial, and
If one denotes a a root of this polynomial in GF(4), the tables of the
operations in GF(4) are the following. There is no table for subtraction, as,
in every field of characteristic 2, subtraction is identical to addition. In
the third table, for the division of x by y, x must be read on the left, and y
on the top. = GF(p2) for an odd prime p=
For applying above general construction of finite fields in the case of GF(p2),
one has to find an irreducible polynomial of degree 2. For p = 2, this
has been done in the preceding section. If p is an odd prime, there are always
irreducible polynomials of the form X2 − r, with r in GF(p).
More precisely, the polynomial X2 − r is irreducible over GF(p) if and only if r
is a quadratic non-residue modulo p. There are quadratic non-residues modulo
p. For example, 2 is a quadratic non-residue for p = 3, 5, 11, 13, ...,
and 3 is a quadratic non-residue for p = 5, 7, 17, .... If p ≡ 3 mod 4, that is p
= 3, 7, 11, 19, ..., one may choose −1 ≡ p − 1 as a quadratic non-residue, which
allows us to have a very simple irreducible polynomial X2 + 1.
Having chosen a quadratic non-residue r, let α be a symbolic square root of r,
that is a symbol which has the property α2 = r, in the same way as the complex
number i is a symbolic square root of −1. Then, the elements of GF(p2) are all
the linear expressions with a and b in GF(p). The operations on
GF(p2) are defined as follows represented by Latin letters are the
operations in GF(p)): = GF(8) and GF(27)=
The polynomial is irreducible over GF(2) and GF(3),
that is, it is irreducible modulo 2 and 3 nor in GF(3)). It follows that the
elements of GF(8) and GF(27) may be represented by expressions
where a, b, c are elements of GF(2) or GF(3), and is a symbol such that
The addition, additive inverse and multiplication on GF(8) and GF(27) may
thus be defined as follows; in following formulas, the operations between
elements of GF(2) or GF(3), represented by Latin letters are the operations in
GF(2) or GF(3), respectively: = GF(16)=
The polynomial is irreducible over GF(2), that is, it
is irreducible modulo 2. It follows that the elements of GF(16) may be
represented by expressions where a, b, c, d are either 0 or 1), and
is a symbol such that As the characteristic of GF(2) is 2,
each element is its additive inverse in GF(16). The addition and multiplication
on GF(16) may be defined as follows; in following formulas, the operations
between elements of GF(2), represented by Latin letters are the operations in
GF(2). Multiplicative structure
The set of non-zero elements in GF(q) is an abelian group under the
multiplication, of order q – 1. By Lagrange's theorem, there exists a
divisor k of q – 1 such that xk = 1 for every non-zero x in GF(q). As the
equation Xk = 1 has at most k solutions in any field, q – 1 is the lowest
possible value for k. The structure theorem of finite abelian groups implies
that this multiplicative group is cyclic, that all non-zero elements are
powers of single element. In summary: The multiplicative group of the non-zero
elements in GF(q) is cyclic, and there exist an element a, such that the q – 1
non-zero elements of GF(q) are a, a2, ..., aq−2, aq−1 = 1.
Such an element a is called a primitive element. Unless q = 2, 3, the primitive
element is not unique. The number of primitive elements is φ(q − 1) where φ
is Euler's totient function. Above result implies that xq = x for
every x in GF(q). The particular case where q is prime is Fermat's little
theorem. = Discrete logarithm=
If a is a primitive element in GF(q), then for any non-zero element x in F,
there is a unique integer n with 0 ≤ n ≤ q − 2 such that
x = an. This integer n is called the discrete
logarithm of x to the base a. While the computation of an is rather
easy, by using, for example, exponentiation by squaring, the
reciprocal operation, the computation of the discrete logarithm is difficult.
This has been used in various cryptographic protocols, see Discrete
logarithm for details. When the nonzero elements of GF(q) are
represented by their discrete logarithms, multiplication and division
are easy, as they reduce to addition and subtraction modulo q – 1. However,
addition amounts to computing the discrete logarithm of am + an. The
identity am + an = an(am−n + 1)
allows one to solve this problem by constructing the table of the discrete
logarithms of an + 1, called Zech's logarithms, for n = 0, ..., q − 2.
Zech's logarithms are useful for large computations, such as linear algebra
over medium-sized fields, that is, fields that are sufficiently large for
making natural algorithms inefficient, but not too large, as one has to
pre-compute a table of the same size as the order of the field.
= Roots of unity= Every nonzero element of a finite field
is a root of unity, as xq−1 = 1 for every nonzero element of GF(q).
If n is a positive integer, a nth primitive root of unity is a solution of
the equation xn = 1 that is not a solution of the equation xm = 1 for any
positive integer m