From Wikipedia, the free encyclopedia

In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains only finitely many elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory. The finite fields are completely known.

Contents 1 Classification 1.1 Examples 1.2 Proof outline 1.3 Detailed proof of the classification 1.3.1 Order 1.3.2 Existence 1.3.3 Uniqueness 2 Explicitly constructing finite fields 2.1 Examples 3 Properties and facts 3.1 Frobenius automorphisms 3.2 Algebraic closure 3.3 Containment 3.4 Finite division rings are fields 4 Multiplicative structure 4.1 Cyclic 4.2 Analog of Fermat's little theorem 5 Applications 6 Some small finite fields 7 See also 8 References 9 External links

There is a unique field of order pⁿ for every prime p and integer , up to isomorphism.

In detail, the finite fields are classified as follows (Jacobson 1985, p. 287):

• 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 integer n ≥ 1, there exists a finite field with pⁿ elements.
• Any two finite fields with the same number of elements are isomorphic. (I.e., 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 GF(pⁿ), where the letters "GF" stand for "Galois field". Another common notation is .

There exists a finite field GF(4) = GF(2²) with 4 elements, and every field with 4 elements is isomorphic to this one. There is also a finite field GF(8) = GF(2³) with 8 elements, and every field with 8 elements is isomorphic to this one. However, there is no field with 6 elements, because 6 is not a prime power.

The simplest case is when the order of the field is prime, i.e., n = 1. This finite field, GF(p), 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 by Z_p, but this may cause confusion because the same notation is used for the ring of p-adic integers.

Even though GF(p) = Z/pZ, the finite field GF(pⁿ) must not be confused with Z/pⁿZ (the ring of integers modulo pⁿ) for n ≥ 2. In fact, for n ≥ 2, the latter is not even a field: for example GF(4) is not the same thing as Z/4Z (the integers modulo 4). (For one thing, in Z/4Z the element 2 (mod 4) has no multiplicative inverse.) Rather, the underlying additive group of GF(4) is isomorphic to the Klein four-group, (Z/2Z)².

The characteristic of a finite field is a prime p (since it has no zero divisors), and the field is a vector space of dimension n over , hence has pⁿ elements.

is a field since p is prime.

Given q = pⁿ, is the splitting field of the polynomial f(T) = T^q − T over .

This field exists and is unique by the construction of splitting fields. The roots are closed under field operations, so the splitting field is exactly the q roots of this polynomial, which are distinct because f' = − 1 has no roots.

Suppose that F is a finite field with additive identity 0 and multiplicative identity 1. The characteristic of F is a prime number p as it is the characteristic of a finite ring without zero divisors. The p (distinct) elements 0, 1, 2, ..., p−1 (where for example 2 means 1+1) form a subfield of F that is isomorphic to . F is a vector space over , and it must have finite dimension over . If the dimension is n, then each element of F is specified uniquely by n coordinates in . There are p possibilities for each coordinate, so the number of elements in F is pⁿ. This proves the first statement.

The proof of the second statement, concerning the existence of a finite field for a given p and n, is more involved. Consider the polynomial f(T) = T^q − T, where q = pⁿ. It is possible to construct a field F (called the splitting field of f), which contains Z/pZ, and which is large enough for f(T) to split completely into linear factors:

where each r_i is an element of F. (The existence of splitting fields in general is discussed in construction of splitting fields.) These q roots are distinct, because f(T) is a polynomial of degree q, and it has no repeated roots because its derivative is

which has no roots in common with f(T). Furthermore, setting R to be the set of these roots,

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

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

and

Therefore R is a field with q elements, proving the second statement.

Finally the uniqueness statement: R is itself the splitting field of f(T), because it is generated over Z/pZ by the roots of f(T), and the splitting field of any polynomial is unique up to isomorphism.

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

The polynomial f(T) = T ² + T + 1 is irreducible over GF(2), and GF(4) = GF(2)[T] / <T²+T+1> can therefore 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 GF(2) (that is, over characteristic 2), we may write this as t² = t + 1. (This follows because −1 = 1 in GF(2)!) 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 the field GF(27), we could start for example with the irreducible polynomial T ³ + T ² + T + 2 over GF(3). We then have GF(27) = {at² + bt + c : a, b, c in GF(3)}, where the multiplication is defined by t ³ + t ² + t + 2 = 0, or by rearranging this equation, t³ = 2t² + 2t + 1.

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

x^q = x

for all x in F. Furthermore, the map

f : F → F

defined by

f(x) = x^p

is bijective and a homomorphism, and is therefore an automorphism. It is called the Frobenius automorphism, after Ferdinand Georg Frobenius.

The Frobenius automorphism has order n, thus the cyclic group it generates is the full group of automorphisms of the field.

Finite fields are not algebraically closed: the polynomial

has no roots over F, as f(α) = 1 for all .

However, for each prime p there is an algebraic closure of the finite fields of characteristic p, as below.

The field GF(pⁿ) contains a copy of GF(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 dimension d, so it must have order (p^m)^d = p^md, so m divides n. "If" is because there exist irreducible polynomials of every degree over GF(p^m).

The direct limit of this system is a field, and is the algebraic closure of the (or indeed for any n), denoted . This is infinite, as it is algebraically closed, or more simply because it contains for all n.

The inclusions commute with the Frobenius map, as it is defined the same way on each field, so the Frobenius map defines an automorphism of , which stabilizes all subfields.

The field can be recovered as the fixed points of the nth power of the Frobenius map.

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

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.)

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).

This means that if F is a finite field with q elements, then there exists an element x in F, called "a generator for the group of units" such that

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

The element x is not unique (unless q = 2 or 3): the set of generators has size where φ 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).

Every element of satisfies x^q = x, which is an analog of Fermat's little theorem, which states that (which is the case q = p).

This follows because the non-zero elements form a group of units of order q − 1, so by Lagrange's theorem x^{q − 1} = 1, so x^q = x (and 0^q = 0); this proof doesn't use that the group of units is cyclic.

Note that conversely, x^q − x is the polynomial used in the construction of the finite field as a splitting field.

Since discrete exponentiation (calculating xⁿ) is fast (by fast exponentiation, such as binary exponentiation, it takes O(logn)), but no fast way of computing the discrete logarithm a is known, which 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.

GF(2):

 + | 0 1        · | 0 1
 --+----        --+----
 0 | 0 1        0 | 0 0
 1 | 1 0        1 | 0 1

GF(3):

 + | 0 1 2       · | 0 1 2
 --+------       --+------
 0 | 0 1 2       0 | 0 0 0
 1 | 1 2 0       1 | 0 1 2
 2 | 2 0 1       2 | 0 2 1

GF(4):

 + | 0 1 A B       · | 0 1 A B
 --+--------       --+--------
 0 | 0 1 A B       0 | 0 0 0 0
 1 | 1 0 B A       1 | 0 1 A B
 A | A B 0 1       A | 0 A B 1
 B | B A 1 0       B | 0 B 1 A

• Finite field arithmetic
• Quasi-finite field
• Trigonometry in Galois fields
• Field with one element

• Jacobson, Nathan (1985), Basic Algebra I (2nd ed.), New York: W. H. Freeman and Co., ISBN 978-0-7167-1480-4

• Finite Fields at Wolfram research.