Finite field
In mathematics, a finite field or Galois field (so-named 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.
"Galois field" redirects here. For Galois field extensions, see Galois extension.
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 pk, 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.
Explicit construction[edit]
Non-prime fields[edit]
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 first chooses an irreducible polynomial P in GF(p)[X] of degree n (such an irreducible polynomial always exists). Then the quotient ring
The six primitive 9th roots of unity are roots of
and are all conjugate under the action of the Galois group.
The twelve primitive 21st roots of unity are roots of
They form two orbits under the action of the Galois group. As the two factors are to each other, a root and its (multiplicative) inverse do not belong to the same orbit.
reciprocal
The 36 primitive elements of GF(64) are the roots of
They split into six orbits of six elements each under the action of the Galois group.
Applications[edit]
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 GF(28). One exception is PDF417 bar code, which is GF(929). Some CPUs have special instructions that can be useful for finite fields of characteristic 2, generally variations of carry-less 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.
Extensions[edit]
Wedderburn's little theorem[edit]
A division ring is a generalization of field. Division rings are not assumed to be commutative. There are no non-commutative 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]
Algebraic closure[edit]
A finite field F is not algebraically closed: the polynomial