Algebraic structures 

In mathematics, a finite field or Galois field (sonamed in honor of Évariste Galois) 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 p when p 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 p and every positive integer k there are fields of order all of which 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.
A finite field is a finite set which is a field; this means that multiplication, addition, subtraction and division (excluding division by zero) are defined and satisfy the rules of arithmetic known as the field axioms.
The number of elements of a finite field is called its order or, sometimes, its size. A finite field of order q exists if and only if q is a prime power p^{k} (where p is a prime number and k is a positive integer). In a field of order p^{k}, adding p copies of any element always results in zero; that is, the characteristic of the field is p.
If q = p^{k}, all fields of order q are isomorphic (see § Existence and uniqueness below).^{[1]} 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 , F_{q} or GF(q), where the letters GF stand for "Galois field".^{[2]}
In a finite field of order q, the polynomial X^{q} − X has all q elements of the finite field as roots. The nonzero elements of a finite field form a multiplicative group. This group is cyclic, so all nonzero elements can be expressed as powers of a single element called a primitive element of the field. (In general there will be several primitive elements for a given field.)
The simplest examples of finite fields are the fields of prime order: for each prime number p, the prime field of order p, , may be constructed as the integers modulo p, Z/pZ.
The elements of the prime field of order p may be represented by integers in the range 0, ..., p − 1. The sum, the difference and the product are the remainder of the division by p of the result of the corresponding integer operation. The multiplicative inverse of an element may be computed by using the extended Euclidean algorithm (see Extended Euclidean algorithm § Modular integers).
Let F be a finite field. For any element x in F and any integer n, denote by n ⋅ x the sum of n copies of x. The least positive n such that n ⋅ 1 = 0 is the characteristic p of the field. This allows defining a multiplication of an element k of GF(p) by an element x of F by choosing an integer representative for k. This multiplication makes F into a GF(p)vector space. It follows that the number of elements of F is p^{n} for some integer n.
The identity
By Fermat's little theorem, if p is a prime number and x is in the field GF(p) then x^{p} = x. This implies the equality
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.
A more general algebraic structure that satisfies all the other axioms of a field, but whose multiplication is not required to be commutative, is called a division ring (or sometimes skew field). By Wedderburn's little theorem, any finite division ring is commutative, and hence is a finite field.
Let q = p^{n} be a prime power, and F be the splitting field of the polynomial
The uniqueness up to isomorphism of splitting fields implies thus that all fields of order q are isomorphic. Also, if a field F has a field of order q = p^{k} as a subfield, its elements are the q roots of X^{q} − X, and F cannot contain another subfield of order q.
In summary, we have the following classification theorem first proved in 1893 by E. H. Moore:^{[1]}
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 X^{q} − X factors as
It follows that GF(p^{n}) contains a subfield isomorphic to GF(p^{m}) if and only if m is a divisor of n; in that case, this subfield is unique. In fact, the polynomial X^{pm} − X divides X^{pn} − X if and only if m is a divisor of n.
Given a prime power q = p^{n} with p prime and n > 1, the field GF(q) may be explicitly constructed in the following way. One first chooses an irreducible polynomial P in GF(p)[X] of degree n (such an irreducible polynomial always exists). Then the quotient ring
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 nonzero 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, one commonly chooses for P a polynomial of the form
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.
The smallest nonprime field is the field with four elements, which is commonly denoted GF(4) 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 GF(2), there is only one irreducible polynomial of degree 2:
Let α denote a root of this polynomial in GF(4). This implies that
and that α and 1 + α are the elements of GF(4) that are not in GF(2). The tables of the operations in GF(4) result from this, and are as follows:
Addition x+y  Multiplication x⋅y  Division x/y  




A table for subtraction is not given, because subtraction is identical to addition, as is the case for every field of characteristic 2. In the third table, for the division of x by y, the values of x must be read in the left column, and the values of y in the top row. (Because 0 ⋅ z = 0 for every z in every ring the division by 0 has to remain undefined.) From the tables, it can be see that the additive structure of GF(4) is isomorphic to the Klein fourgroup, while the nonzero multiplicative structure is isomorphic to Z_{3}.
The map
For applying the above general construction of finite fields in the case of GF(p^{2}), 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 X^{2} − r, with r in GF(p).
More precisely, the polynomial X^{2} − r is irreducible over GF(p) if and only if r is a quadratic nonresidue modulo p (this is almost the definition of a quadratic nonresidue). There are p − 1/2 quadratic nonresidues modulo p. For example, 2 is a quadratic nonresidue for p = 3, 5, 11, 13, ..., and 3 is a quadratic nonresidue 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 nonresidue, which allows us to have a very simple irreducible polynomial X^{2} + 1.
Having chosen a quadratic nonresidue 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(p^{2}) are all the linear expressions
The polynomial
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:
The polynomial
The field GF(16) has eight primitive elements (the elements that have all nonzero elements of GF(16) as integer powers). These elements are the four roots of and their multiplicative inverses. In particular, α is a primitive element, and the primitive elements are with m less than and coprime with 15 (that is, 1, 2, 4, 7, 8, 11, 13, 14).
The set of nonzero 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 x^{k} = 1 for every nonzero x in GF(q). As the equation x^{k} = 1 has at most k solutions in any field, q – 1 is the highest possible value for k. The structure theorem of finite abelian groups implies that this multiplicative group is cyclic, that is, all nonzero elements are powers of a single element. In summary:
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.
The result above implies that x^{q} = x for every x in GF(q). The particular case where q is prime is Fermat's little theorem.
If a is a primitive element in GF(q), then for any nonzero element x in F, there is a unique integer n with 0 ≤ n ≤ q − 2 such that
This integer n is called the discrete logarithm of x to the base a.
While a^{n} can be computed very quickly, for example using exponentiation by squaring, there is no known efficient algorithm for computing the inverse operation, the discrete logarithm. 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 a^{m} + a^{n}. The identity
allows one to solve this problem by constructing the table of the discrete logarithms of a^{n} + 1, called Zech's logarithms, for n = 0, ..., q − 2 (it is convenient to define the discrete logarithm of zero as being −∞).
Zech's logarithms are useful for large computations, such as linear algebra over mediumsized fields, that is, fields that are sufficiently large for making natural algorithms inefficient, but not too large, as one has to precompute a table of the same size as the order of the field.
Every nonzero element of a finite field is a root of unity, as x^{q−1} = 1 for every nonzero element of GF(q).
If n is a positive integer, an nth primitive root of unity is a solution of the equation x^{n} = 1 that is not a solution of the equation x^{m} = 1 for any positive integer m < n. If a is a nth primitive root of unity in a field F, then F contains all the n roots of unity, which are 1, a, a^{2}, ..., a^{n−1}.
The field GF(q) contains a nth primitive root of unity if and only if n is a divisor of q − 1; if n is a divisor of q − 1, then the number of primitive nth roots of unity in GF(q) is φ(n) (Euler's totient function). The number of nth roots of unity in GF(q) is gcd(n, q − 1).
In a field of characteristic p, every (np)th root of unity is also a nth root of unity. It follows that primitive (np)th roots of unity never exist in a field of characteristic p.
On the other hand, if n is coprime to p, the roots of the nth cyclotomic polynomial are distinct in every field of characteristic p, as this polynomial is a divisor of X^{n} − 1, whose discriminant is nonzero modulo p. It follows that the nth cyclotomic polynomial factors over GF(p) into distinct irreducible polynomials that have all the same degree, say d, and that GF(p^{d}) is the smallest field of characteristic p that contains the nth primitive roots of unity.
The field GF(64) has several interesting properties that smaller fields do not share: it has two subfields such that neither is contained in the other; not all generators (elements with minimal polynomial of degree 6 over GF(2)) are primitive elements; and the primitive elements are not all conjugate under the Galois group.
The order of this field being 2^{6}, and the divisors of 6 being 1, 2, 3, 6, the subfields of GF(64) are GF(2), GF(2^{2}) = GF(4), GF(2^{3}) = GF(8), and GF(64) itself. As 2 and 3 are coprime, the intersection of GF(4) and GF(8) in GF(64) is the prime field GF(2).
The union of GF(4) and GF(8) has thus 10 elements. The remaining 54 elements of GF(64) generate GF(64) in the sense that no other subfield contains any of them. It follows that they are roots of irreducible polynomials of degree 6 over GF(2). This implies that, over GF(2), there are exactly 9 = 54/6 irreducible monic polynomials of degree 6. This may be verified by factoring X^{64} − X over GF(2).
The elements of GF(64) are primitive nth roots of unity for some n dividing 63. As the 3rd and the 7th roots of unity belong to GF(4) and GF(8), respectively, the 54 generators are primitive nth roots of unity for some n in {9, 21, 63}. Euler's totient function shows that there are 6 primitive 9th roots of unity, 12 primitive 21st roots of unity, and 36 primitive 63rd roots of unity. Summing these numbers, one finds again 54 elements.
By factoring the cyclotomic polynomials over GF(2), one finds that:
This shows that the best choice to construct GF(64) is to define it as GF(2)[X] / (X^{6} + X + 1). In fact, this generator is a primitive element, and this polynomial is the irreducible polynomial that produces the easiest Euclidean division.
In this section, p is a prime number, and q = p^{n} is a power of p.
In GF(q), the identity (x + y)^{p} = x^{p} + y^{p} implies that the map
Denoting by φ^{k} the composition of φ with itself k times, we have
There are no other GF(p)automorphisms of GF(q). In other words, GF(p^{n}) has exactly n GF(p)automorphisms, which are
In terms of Galois theory, this means that GF(p^{n}) is a Galois extension of GF(p), which has a cyclic Galois group.
The fact that the Frobenius map is surjective implies that every finite field is perfect.
Main article: Factorization of polynomials over finite fields 
If F is a finite field, a nonconstant monic polynomial with coefficients in F is irreducible over F, if it is not the product of two nonconstant monic polynomials, with coefficients in F.
As every polynomial ring over a field is a unique factorization domain, every monic polynomial over a finite field may be factored in a unique way (up to the order of the factors) into a product of irreducible monic polynomials.
There are efficient algorithms for testing polynomial irreducibility and factoring polynomials over finite field. They are a key step for factoring polynomials over the integers or the rational numbers. At least for this reason, every computer algebra system has functions for factoring polynomials over finite fields, or, at least, over finite prime fields.
The polynomial
This implies that, if q = p^{n} then X^{q} − X is the product of all monic irreducible polynomials over GF(p), whose degree divides n. In fact, if P is an irreducible factor over GF(p) of X^{q} − X, its degree divides n, as its splitting field is contained in GF(p^{n}). Conversely, if P is an irreducible monic polynomial over GF(p) of degree d dividing n, it defines a field extension of degree d, which is contained in GF(p^{n}), and all roots of P belong to GF(p^{n}), and are roots of X^{q} − X; thus P divides X^{q} − X. As X^{q} − X does not have any multiple factor, it is thus the product of all the irreducible monic polynomials that divide it.
This property is used to compute the product of the irreducible factors of each degree of polynomials over GF(p); see Distinct degree factorization.
The number N(q, n) of monic irreducible polynomials of degree n over GF(q) is given by^{[4]}
By the above formula, the number of irreducible (not necessarily monic) polynomials of degree n over GF(q) is (q − 1)N(q, n).
The exact formula implies the inequality
In cryptography, the difficulty of the discrete logarithm problem in finite fields or in elliptic curves is the basis of several widely used protocols, such as the Diffie–Hellman protocol. For example, in 2014, a secure internet connection to Wikipedia involved the elliptic curve Diffie–Hellman protocol (ECDHE) over a large finite field.^{[5]} In coding theory, many codes are constructed as subspaces of vector spaces over finite fields.
Finite fields are used by many error correction codes, such as Reed–Solomon error correction code or BCH code. The finite field almost always has characteristic of 2, since computer data is stored in binary. For example, a byte of data can be interpreted as an element of . One exception is PDF417 bar code, which is . Some CPUs have special instructions that can be useful for finite fields of characteristic 2, generally variations of carryless product.
Finite fields are widely used in number theory, as many problems over the integers may be solved by reducing them modulo one or several prime numbers. For example, the fastest known algorithms for polynomial factorization and linear algebra over the field of rational numbers proceed by reduction modulo one or several primes, and then reconstruction of the solution by using Chinese remainder theorem, Hensel lifting or the LLL algorithm.
Similarly many theoretical problems in number theory can be solved by considering their reductions modulo some or all prime numbers. See, for example, Hasse principle. Many recent developments of algebraic geometry were motivated by the need to enlarge the power of these modular methods. Wiles' proof of Fermat's Last Theorem is an example of a deep result involving many mathematical tools, including finite fields.
The Weil conjectures concern the number of points on algebraic varieties over finite fields and the theory has many applications including exponential and character sum estimates.
Finite fields have widespread application in combinatorics, two well known examples being the definition of Paley Graphs and the related construction for Hadamard Matrices. In arithmetic combinatorics finite fields^{[6]} and finite field models^{[7]}^{[8]} are used extensively, such as in Szemerédi's theorem on arithmetic progressions.
A finite field F is not algebraically closed: the polynomial
Fix an algebraic closure of . The map sending each x to x^{q} is called the qth power Frobenius automorphism. The subfield of fixed by the nth iterate of is the set of zeros of the polynomial x^{qn} − x, which has distinct roots since its derivative in is −1, which is never zero. Therefore that subfield has q^{n} elements, so it is the unique copy of in . Every finite extension of in is this for some n, so
Although finite fields are not algebraically closed, they are quasialgebraically closed, which means that every homogeneous polynomial over a finite field has a nontrivial zero whose components are in the field if the number of its variables is more than its degree. This was a conjecture of Artin and Dickson proved by Chevalley (see Chevalley–Warning theorem).
A division ring is a generalization of field. Division rings are not assumed to be commutative. There are no noncommutative finite division rings: Wedderburn's little theorem states that all finite division rings are commutative, and hence are finite fields. This result holds even if we relax the associativity axiom to alternativity, that is, all finite alternative division rings are finite fields, by the Artin–Zorn theorem.^{[9]}