In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory. The finite fields are classified by size; there is exactly one finite field up to isomorphism of size p^k for each prime p and positive integer k. Each finite field of size q is the splitting field of the polynomial x^q - x, and thus the fixed field of the Frobenius endomorphism which takes x to x^q. Similarly, the multiplicative group of the field is a cyclic group. Wedderburn's little theorem states that the Brauer group of a finite field is trivial, so that every finite division ring is a finite field. Finite fields have applications in many areas of mathematics and computer science, including coding theory, LFSRs, modular representation theory, and the groups of Lie type. Finite fields are an active area of research, including recent results on the Kakeya conjecture and open problems on the size of the smallest primitive root.

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.

Classification

The finite fields are classified as follows :

The order, or number of elements, of a finite field is of the form pⁿ, where p is a prime number called the characteristic of the field, and n is a positive integer.

For every prime number p and positive integer n, there exists a finite field with pⁿ elements.

Any two finite fields with the same number of elements are isomorphic. That is, under some renaming of the elements of one of these, both its addition and multiplication tables become identical to the corresponding tables of the other one.

This classification justifies using a naming scheme for finite fields that specifies only the order of the field. One notation for a finite field is F_pⁿ. Another notation is GF(pⁿ), where the letters "GF" stand for "Galois field".

Examples

First we consider fields where the size is prime, i.e., n = 1. Such a field is also called a Prime field. An example of such a finite field is the ring Z/pZ. It is a finite field with p elements, usually labelled 0, 1, 2, ..., p−1, where arithmetic is performed modulo p. It is also sometimes denoted Z_p, but within some areas of mathematics, particularly number theory, this may cause confusion because the same notation Z_p is used for the ring of p-adic integers.

Next we consider fields where the size is not prime, but is a prime power, i.e., n > 1. Two isomorphic constructions of the field with 4 elements are (Z/2Z)[T]/(T²+T+1) and Z[φ]/(2Z), where φ = $\backslash frac\{-1\; +\; \backslash sqrt\{5\}\}\{2\}$. A field with 8 elements is (Z/2Z)[T]/(T³+T+1). Two isomorphic constructions of the field with 9 elements are (Z/3Z)[T]/(T²+1) and Z[i]/(3Z).

Even though all fields of size p are isomorphic to Z/pZ, for n ≥ 2 the ring Z/pⁿZ (the ring of integers modulo pⁿ) is not a field. The element p (mod pⁿ) is nonzero and has no multiplicative inverse. By comparison with the ring Z/4Z of size 4, the underlying additive group of the field (Z/2Z)[T]/(T²+T+1) of size 4 is not cyclic but rather is isomorphic to the Klein four-group, (Z/2Z)².

A prime power field with n=2 is also called a binary field.

Finally, we consider fields where the size is not a prime power. As it turns out, none exist. For example, there is no field with 6 elements, because 6 is not a prime power. Each and every pair of operations on a set of 6 elements fails to satisfy the mathematical definition of a field.

Proof outline

The characteristic of a finite field is a prime p (since a field has no zero divisors), and the field is a vector space of some finite dimension, say n, over Z/pZ, hence the field has pⁿ elements. A field of order p exists, because F_p = Z/pZ is a field, where primality is required for the nonzero elements to have multiplicative inverses.

For any prime power q = pⁿ, F_q is the splitting field of the polynomial f(T) = T^q − T over F_p. This field exists and is unique up to isomorphism by the construction of splitting fields. The set of roots is a field, the fixed field of the nth iterate of the Frobenius endomorphism, so the splitting field is exactly the q roots of this polynomial, which are distinct because the polynomial T^q − T is separable over F_p: its derivative is −1, which has no roots.

Detailed proof of the classification

Order

We give two proofs that a finite field has prime-power order.

For the first proof, let F be a finite field. Write its additive identity as 0 and its multiplicative identity as 1. The characteristic of F is a prime number p as the characteristic of a finite ring is positive and must be prime or else the ring would have zero divisors. The p distinct elements 0, 1, 2, ..., p−1 (where 2 means 1+1, etc.) form a subfield of F that is isomorphic to Z/pZ. F is a vector space over Z/pZ, and it must have finite dimension over Z/pZ. Call the dimension n, so each element of F is specified uniquely by n coordinates in Z/pZ. There are p possibilities for each coordinate, with no dependencies among different coordinates, so the number of elements in F is pⁿ. This proves the first statement, and does a little more: it shows that, additively, F is a direct sum of copies of Z/pZ.

For the second proof, which is longer than the one above, we look more closely at the additive structure of a finite field. When F is a finite field and a and b are any two nonzero elements of F, the function f(x) = (b/a)x on F is an additive automorphism which sends a to b. (It certainly is not multiplicative too, in general!) So F is, under addition, a finite abelian group in which any two nonidentity elements are linked by an automorphism. Let's show that for any nontrivial finite abelian group A where any two nonzero elements are linked by an automorphism of A, the size of A must be a prime power. Let p be a prime factor of the size of A. By Cauchy's theorem, there is an element a of A of order p. Since we are assuming for every nonzero b in A there is an automorphism f of A such that f(a) = b, b must have order p as well. Hence all nonzero elements in A have order p. If q were any prime dividing the size of A, by Cauchy's theorem there is an element in A of order q, and since we have shown all nonzero elements have order p it follows that q = p. Thus p is the only prime factor of the size of A, so A has order equal to a power of p.

Remark: In that group-theoretic argument, one could remove the assumption that A is abelian and directly show A has to be abelian. That is, if G is a nontrivial finite group in which all nonidentity elements are linked by an automorphism, G must be an abelian group of p-power order for some prime p. The prime-power order argument goes as above, and once we know G is a p-group we appeal once again to the automorphism-linking condition, as follows. Since G is a nontrivial finite p-group, it has a nontrivial center. Pick a nonidentity element g in the center. For any h in G, there is an automorphism of G sending g to h, so h has to be in the center too. An automorphism of a group preserves the center. Therefore all elements of G are in its center, so G is abelian.

We can go further with this and show A has to be a direct sum of cyclic groups of order p. From the classification of finite abelian p-groups, A is a direct sum of cyclic groups of p-power order. Since all nonzero elements of A have order p, the cyclic groups in such a direct sum decomposition can't have order larger than p, so they all have order p. Returning to the motivating application where A is F as an additive group, we have recovered the fact that F is a direct sum of copies of Z/pZ (cyclic group of order p).

Now the first proof, using linear algebra, is a lot shorter and is the standard argument found in (nearly) all textbooks that treat finite fields. The second proof is interesting because it gets the same result by working much more heavily with the additive structure of a finite field. Of course we had to use the multiplicative structure somewhere (after all, not all finite rings have prime-power order), and it was used right at the start: multiplication by b/a on F sends a to b. The second proof is actually the one which was used in E. H. Moore's 1903 paper which (for the first time) classified all finite fields.

Existence

The proof of the second statement, concerning the existence of a finite field of size q = pⁿ for any prime p and positive integer n, is more involved. We again give two arguments.

The case n = 1 is easy: take F_p = Z/pZ.

For general n, inside F_p[T] consider the polynomial f(T) = T^q − T. It is possible to construct a field F (called the splitting field of f over F_p), which contains F_p and which is large enough for f(T) to split completely into linear factors: :f(T) = (T−r₁)(T−r₂)⋯(T−r_q) in F[T]. The existence of splitting fields in general is discussed in construction of splitting fields. These q roots are distinct, because T^q − T is a polynomial of degree q which has no repeated roots in F: its derivative is qT^q−1 − 1, which is −1 (because q = 0 in F) and therefore the derivative has no roots in common with f(T). Furthermore, setting R to be the set of these roots, : R = { r₁, ..., r_q } = { roots of the equation T^q = T } one sees that R itself forms a field, as follows. Both 0 and 1 are in R, because 0^q = 0 and 1^q = 1. If r and s are in R, then :(r+s)^q = r^q + s^q = r + s so that r+s is in R. The first equality above follows from the binomial theorem and the fact that F has characteristic p. Therefore R is closed under addition. Similarly, R is closed under multiplication and taking inverses, because : (rs)^q = r^q s^q = rs and : (r⁻¹)^q = (r^q)⁻¹ = r⁻¹. Therefore R is a field with q elements, proving the second statement.

For the second proof that a field of size q = pⁿ exists, we just sketch the ideas. We will give a combinatorial argument that a monic irreducible f(T) of degree n exists in F_p[T]. Then the quotient ring F_p[T] / (f(T)) is a field of size q. Because T^q − T has no repeated irreducible factors (it is a separable polynomial in F_p[T]), it is a product of distinct monic irreducibles. We ask: which monic irreducibles occur in the factorization? Using some group theory, one can show that a monic irreducible in F_p[T] is a factor precisely when its degree divides n. Writing N_p(d) for the number of monic irreducibles of degree d in F_p[T], computing the degree of the irreducible factorization of T^q − T shows q = pⁿ is the sum of dN_p(d) over all d dividing n. This holds for all n, so by Moebius inversion one can get a formula for N_p(n) for all n, and a simple lower bound estimate using this formula shows N_p(n) is positive. Thus a (monic) irreducible of degree n in F_p[T] exists, for any n.

Uniqueness

Finally the uniqueness statement: a field of size q = pⁿ is the splitting field of T^q - T over its subfield of size p, and for any field K, two splitting fields of a polynomial in K[T] are unique up to isomorphism over K. That is, the two splitting fields are isomorphic by an isomorphism extending the identification of the copies of K inside the two splitting fields. Since a field of size p can be embedded in a field of characteristic p in only one way (the multiplicative identity 1 in the field is unique, then 2 = 1 + 1, and so on up to p - 1), the condition of two fields of size q being isomorphic over their subfields of size p is the same as just being isomorphic fields.

Warning: it is not the case that two finite fields of the same size are isomorphic in a unique way, unless the fields have size p. Two fields of size pⁿ are isomorphic to each other in n ways (because a field of size pⁿ is isomorphic to itself in n ways, from Galois theory for finite fields).

Explicitly constructing finite fields

Given a prime power q = pⁿ, we may explicitly construct a finite field with q elements as follows. Select a monic irreducible polynomial f(T) of degree n in F_p[T]. (Such a polynomial is guaranteed to exist, once we know that a finite field of size q exists: just take the minimal polynomial of any primitive element for that field over the subfield F_p.) Then F_p[T]/(f(T)) is a field of size q. Here, F_p[T] denotes the ring of all polynomials in T with coefficients in F_p, (f(T)) denotes the ideal generated by f(T), and the quotient is meant in the sense of quotient rings — the set of polynomials in T with coefficients in F_p modulo (f(T)).

Examples

The polynomial f(T) = T ² + T + 1 is irreducible over Z/2Z, and (Z/2Z)[T] / (T²+T+1) has size 4. Its elements can be written as the set {0, 1, t, t+1} where the multiplication is carried out by using the relation t² + t + 1 = 0. In fact, since we are working over Z/2Z (that is, in characteristic 2), we may write this as t² = t + 1. (This follows because −1 = 1 in Z/2Z) Then, for example, to determine t³, we calculate: t³ = t(t²) = t(t+1) = t²+t = t+1+t = 2t + 1 = 1, so t³ = 1.

In order to find the multiplicative inverse of t in this field, we have to find a polynomial p(T) such that T * p(T) = 1 modulo T ² + T + 1. The polynomial p(T) = T + 1 works, and hence 1/t = t + 1.

To construct a field of size 27, we could start for example with the irreducible polynomial T ³ + T ² + T + 2 over Z/3Z. The field (Z/3Z)[T]/(T ³ + T ² + T + 2) has size 27. Its elements have the form at² + bt + c where a, b, and c lie in Z/3Z and the multiplication is defined by t ³ + t ² + t + 2 = 0, or by rearranging this equation, t³ = 2t² + 2t + 1.

Properties and facts

Frobenius automorphisms

If F is a finite field with q = pⁿ elements (where p is prime), then

:x^q = x

for all x in F (see Analog of Fermat's little theorem below). Furthermore, the map

:f : F → F

defined by

:f(x) = x^p

is bijective and a homomorphism, and is therefore an automorphism on the field F which fixes the subfield with p elements. It is called the Frobenius automorphism, after Ferdinand Georg Frobenius.

The Frobenius automorphism of a field of size pⁿ has order n, and the cyclic group it generates is the full group of automorphisms of the field.

Algebraic closure

Finite fields are not algebraically closed: the polynomial :$f(T)=1+\backslash prod\_\{\backslash alpha\; \backslash in\; F\}\backslash left(T-\backslash alpha\backslash right)$ has no roots over F, as f(α) = 1 for all α in F. However, for each prime p there is an algebraic closure of any finite field of characteristic p, as below.

Containment

The field F_pⁿ contains a copy of F_p^m if and only if m divides n. "Only if" is because the larger field is a vector space over the smaller field, of some finite dimension, say d, so it must have size $(p^m)^d=p^\{md\}$, so m divides n. "If" is because there exist irreducible polynomials of every degree over F_p^m.

The direct limit of this system is a field, and is an algebraic closure of F_p (or indeed of F_pⁿ for any n), denoted $\backslash bar\backslash mathbf\{F\}\_p$. This field is infinite, as it is algebraically closed, or more simply because it contains a subfield of size pⁿ for all n.

The inclusions commute with the Frobenius map, as it is defined the same way on each field (it is still just the function raising to the pth power), so the Frobenius map defines an automorphism of $\backslash bar\backslash mathbf\{F\}\_p$, which carries all subfields back to themselves. Unlike in the case of finite fields, the Frobenius automorphism on the algebraic closure of F_p has infinite order (no iterate of it is the identity function on the whole field), and it does not generate the full group of automorphisms of this field. That is, there are automorphisms of the algebraic closure which are not iterates of the pth power map. However, the iterates of the pth power map do form a dense subgroup of the automorphism group in the Krull topology. Algebraically, this corresponds to the additive group Z being dense in the profinite integers (direct product of the p-adic integers over all primes p, with the product topology).

The field F_pⁿ can be recovered as the fixed points of the nth iterate of the Frobenius map.

If we actually construct our finite fields in such a fashion that F_pⁿ is contained in F_p^m whenever n divides m, then this direct limit can be constructed as the union of all these fields. Even if we do not construct our fields this way, we can still speak of the algebraic closure, but some more delicacy is required in its construction.

Irreducibility of polynomials

If F is a finite field, a polynomial f(X) with coefficients in F is said to be irreducible over F if and only if f(X) is irreducible as an element of the polynomial ring over F (that is, in F[X]). Note that since the polynomial ring F[X] is a unique factorization domain, a polynomial f(X) is irreducible if and only if it is prime as an element of F[X].

There are several fundamental questions one can ask about irreducible polynomials over a given finite field. Firstly, is it possible to give an explicit formula, in the variables q and n, that yields the number of irreducible polynomials over GF(q) of degree n? Note that since there are only finitely many polynomials of a given degree n over the Galois field GF(q), there can be only finitely many such irreducible polynomials. However, while little theory is required to compute the number of polynomials of degree n over GF(q) (there are precisely qⁿ(q−1) such polynomials), it is not immediately obvious how to compute the number of irreducible polynomials of degree n over q.

Secondly, is it possible to describe an algorithm that may be used to decide whether a given polynomial over GF(q) is irreducible? In fact, there exists two such (known) algorithms: the Berlekamp algorithm and the Cantor-Zassenhaus algorithm. Furthermore, these algorithms do much more than merely decide whether a given polynomial is irreducible; they may also be implemented to explicitly compute the irreducible factors of f.

Number of monic irreducible polynomials of a given degree over a finite field

If GF(q) denotes the finite field of order q, then the number N of monic irreducible polynomials of degree n over GF(q) is given by:

:$N(q,n)=\backslash frac\{1\}\{n\}\backslash sum\_\{d|n\}\; \backslash mu(d)q^\{\backslash frac\{n\}\{d\}\},$

where μ is the Möbius function. By the above formula, the number of irreducible polynomials of degree n over GF(q) is given by $(q-1)N(q,n)$. A (slightly simpler) lower bound on N also exists, and is given by:

:$N\backslash geq\backslash frac\{1\}\{n\}\; \backslash left(q^n-\backslash sum\_\{p|n,\; \backslash ;\; p\; \backslash text\{\; prime\; \}\}\; q^\{\backslash frac\{n\}\{p\}\}\backslash right)$

Algorithm for computing the irreducible factors of a given polynomial over a finite field

Wedderburn's little theorem

A division ring is a generalization of field, which are not assumed commutative. There are no non-commutative finite division rings: Wedderburn's little theorem states that all finite division rings are commutative, hence finite fields. The result holds even if we relax associativity and consider alternative rings, by the Artin–Zorn theorem.

Multiplicative structure

Cyclic

The multiplicative group of every finite field is cyclic, a special case of a theorem mentioned in the article about fields (see Field (mathematics)#Some first theorems). A generator for the multiplicative group is a primitive element.

This means that if F is a finite field with q elements, then there exists an element x in F such that

:F = { 0, 1, x, x², ..., x^q-2 }.

The primitive element x is not unique (unless q = 2 or 3): the set of generators has size $\backslash varphi(q-1)$ where $\backslash phi$ is Euler's totient function. If we fix a generator, then for any non-zero element a in F_q, there is a unique integer n with

:0 ≤ n ≤ q − 2

such that

:a = xⁿ.

The value of n for a given a is called the discrete log of a (in the given field, to base x).

Analog of Fermat's little theorem

Every element of a field of size q satisfies a^q = a. When q is prime, this is just Fermat's little theorem, which states that a^p ≡ a (mod p) for any integer a and prime p.

The general statement for any finite field follows because the non-zero elements in a field of size q form a group under multiplication of order q−1, so by Lagrange's theorem a^q−1 = 1 for any nonzero a in the field. Then a^q = a and this holds for 0 as well.

Applications

Discrete exponentiation, also known as calculating a = xⁿ from x and n, can be computed quickly using techniques of fast exponentiation such as binary exponentiation, which takes only O(log n) field operations. No fast way of computing the discrete logarithm n given a and x is known, and this has many applications in cryptography, such as the Diffie-Hellman protocol.

Finite fields also find applications in coding theory: many codes are constructed as subspaces of vector spaces over finite fields.

Within number theory, the significance of finite fields is their role in the definition of the Frobenius element (or, more accurately, Frobenius conjugacy class) attached to a prime ideal in a Galois extension of number fields, which in turn is needed to make sense of Artin L-functions of representations of the Galois group, the non-abelian generalization of Dirichlet L-functions.

Counting solutions to equations over finite fields leads into deep questions in algebraic geometry, the Weil conjectures, and in fact was the motivation for Grothendieck's development of modern algebraic geometry.

Some small finite fields

F₂: {| |- |

+ !! 0 !! 1
! 0	0	1
1	1	0

|

× !! 0 !! 1
! 0	0	0
1	0	1

|}

F₃: {| |- |

+ !! 0 !! 1 !! 2
! 0	0	1	2
1	1	2	0
2	2	0	1

|

× !! 0 !! 1 !! 2
! 0	0	0	0
1	0	1	2
2	0	2	1

|}

F₄: {| |- |

+ !! 0 !! 1 !! A !! B
! 0	0	1	A
1	1	0	B
A	A	B	0
B	B	A	1

|

× !! 0 !! 1 !! A !! B
! 0	0	0	0
1	0	1	A
A	0	A	B
B	0	B	1

|}

See also

Finite field arithmetic

Quasi-finite field

Trigonometry in Galois fields

Field with one element

Notes

References

External links

Finite Fields at Wolfram research.

Category:Field theory

ar:حقل منته ca:Cos finit cs:Konečné těleso de:Endlicher Körper el:Πεπερασμένο σώμα es:Cuerpo finito fr:Corps fini ko:유한체 it:Campo finito he:שדה סופי nl:Eindig lichaam (Ned) / Eindig veld (Be) ja:有限体 pl:Ciało skończone pt:Corpo finito ro:Corp finit ru:Конечное поле simple:Galois field fi:Äärellinen kunta uk:Поле Галуа ur:متناہی میدان zh-yue:有限體 zh:有限域