FINITE FIELD

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

Classification

Examples

Proof of the classification

Explicitly constructing finite fields

Examples

Properties and facts

Applications

Some small finite fields

See also

References

External links

Classification

The finite fields are classified as follows :

★ The 'order', or number of elements, of a finite field is of the form ''p''^''n'', 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''^''n'' elements.

★ Any two finite fields with the same number of elements are isomorphic (that is, their addition tables are essentially the same, and their multiplication tables are essentially the same).
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''^''n''), where the letters "GF" stand for "Galois field". Another common notation is $mathbb\; F\_\{p^n\}$.

Examples

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 finite field with 6 elements, because 6 is not a power of any prime.
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'/''p'''Z'. 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'/''p'''Z', the finite field 'GF'(''p''^''n'') must not be confused with 'Z'/''p''^''n'''Z' (the ring of integers modulo ''p''^''n'') 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'/4'Z' (the integers modulo 4). Rather, the underlying additive group of 'GF'(4) is isomorphic to the Klein four-group, ('Z'/2'Z')².

Proof of the classification

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 'Z'/''p'''Z'. ''F'' is a vector space over 'Z'/''p'''Z', and it must have finite dimension over 'Z'/''p'''Z'. If the dimension is ''n'', then each element of ''F'' is specified uniquely by ''n'' coordinates in 'Z'/''p'''Z'. There are ''p'' possibilities for each coordinate, so the number of elements in ''F'' is ''p''^''n''. 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''^''n''. It is possible to construct a field ''F'' (called the splitting field of ''f''), which contains 'Z'/''p'''Z', and which is large enough for ''f''(''T'') to split completely into linear factors:
: $f(T)\; =\; (T-r\_1)(T-r\_2)cdots(T-r\_q),\; ,!$
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
: $qT^\{q-1\}\; -\; 1\; equiv\; -1\; pmod\; p,\; ,!$
which has no roots in common with ''f''(''T''). Furthermore, setting ''R'' to be the set of these roots,
: $R\; =\; \{r\_1,\; ldots,\; r\_q\}\; =\; \{mbox\{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^\{-1\})^q\; =\; (r^q)^\{-1\}\; =\; r^\{-1\}.\; ,!$
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'/''p'''Z' by the roots of ''f''(''T''), and the splitting field of any polynomial is unique up to isomorphism.

Explicitly constructing finite fields

Given a prime power ''q'' = ''p''^''n'', we may explicitly construct 'GF'(''q''), the finite field with ''q'' elements, as follows. Select an irreducible polynomial ''f''(''T'') of degree ''n'' with coefficients in 'GF'(''p''). (Such an ''f'' is guaranteed to exist, once we know that the finite field 'GF'(''q'') exists: just take the minimal polynomial of any element that generates 'GF'(''q'') over the subfield 'GF'(''p'').) Then 'GF'(''q'') = 'GF'(''p'')[''T''] / <''f''(''T'')>. Here, 'GF'(''p'')[''T''] denotes the ring of all polynomials with coefficients in 'GF'(''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 with coefficients in 'GF'(''p'') on division by ''f''(''T'').

Examples

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''³ = 2''t''² + 2''t'' + 1.

Properties and facts

If ''F'' is a finite field with ''q'' = ''p''^''n'' 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.
The field 'GF'(''p^m'') contains a copy of 'GF'(''pⁿ'') if and only if ''n'' divides ''m''. The reason for the if direction is that there exist irreducible polynomials of every degree over 'GF'(''p^m'').
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 we can form the union of all these fields. This union is also a field, albeit an infinite one. It is the algebraic closure of each of the fields 'GF'(''pⁿ''). 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.
For all fields multiplication is commutative. For finite fields however commutativity of multiplication can be shown to follow from the other properties of a field. Division rings are algebraic structures more general than fields, as they are not assumed to be necessarily commutative. Wedderburn's (little) theorem states that all finite division rings are commutative, hence finite fields.

Applications

The multiplicative group of every finite field is cyclic, a special case of a theorem mentioned here in the article about fields. This means that if ''F'' is a finite field with ''q'' elements, then there always exists an element ''x'' in ''F'' such that
:''F'' = { 0, 1, ''x'', ''x''², ..., ''x''^''q''-2 }.
Unless ''q'' = 2 or 3, the element ''x'' is not unique. If we fix one, 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''^''n''.
The value of ''n'' for a given ''a'' is called the ''discrete log'' of ''a'' (in the given field, to base ''x''). In practice, although calculating ''x''^''n'' is relatively trivial given ''n'', finding ''n'' for a given ''a'' is (under current theories) a computationally difficult process, and has many applications in cryptography.
Finite fields also find applications in coding theory: many codes are constructed as subspaces of vector spaces over finite fields.

Some small 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

See also

★ Finite field arithmetic

★ Quasi-finite field

★ Trigonometry in Galois fields

References

★

External links

★ Finite Fields at Wolfram research.