Finite field
In algebra, a branch of mathematics, a finite body or Galois body (after Évariste Galois) is a body with a finite number of elements, i.e., a finite set on which two basic operations understood as addition and multiplication are defined such that the set together with these operations satisfies all the requirements of a body.
Finite fields play an important role in cryptography and coding theory (forward error correction, for example in the Reed-Solomon code). Besides, they are fundamental for the study of the prime ideals in the ring of integers of a finite body extension of in the context of algebraic number theory. Compare also branching in the context of extensions of Dedekind rings.
Moreover, finite bodies are important in geometry as coordinate domains of finite geometries. They are more general coordinate spaces of planes and spaces in synthetic geometry. With the help of addition and multiplication in a finite body, links with weaker algebraic properties are defined here, which turn the body into, for example, a ternary or quasibody. Projective and affine planes can then be constructed on these generalized solids.
The number of elements of a finite body is always a prime power. For every prime number and every positive natural number
there exists (except for isomorphism) exactly one body with
elements, which is denoted by
or
is denoted.
is the body of residue classes of integers modulo
.
E. H. Moore probably coined the English term Galois field in 1893 in honor of Évariste Galois, who already calculated with certain imaginary numbers modulo
Wedderburn's theorem states that multiplication in a finite skew body is necessarily commutative. This means that finite skew bodies are always finite bodies.
Example: The body with 2 elements
The residue classes modulo form the body with two elements.
represent the residue class
of even numbers,
class
of the odd numbers. For addition holds:
For multiplication applies:
and
Classification of finite bodies
If is a finite body, then the kernel of the ring homomorphism
,
always of the form
with some prime number
, i.e., it consists of all multiples of
. Note that 1 is not a prime number. This prime
is called the characteristic of
. According to the homomorphism theorem for rings, the image of
is isomorphic to the residue class body
and is called the prime body of
. As a finite extension body,
also an
-dimensional vector space over its prime body. Thus
exactly
elements.
In a body with characteristic
: K because of
a homomorphism of additive groups.
The remaining summands occurring on the right-hand side according to the binomial formula drop because of for
homorphism in honor of Ferdinand Georg Frobenius, which is an automorphism and therefore also called Frobenius automorphism. The prime body is pointwise fixed by
(in fact, for example,
is a multiple of 7). Similarly,
on any body with
elements. On the other hand,
as a polynomial of degree
at most
distinct zeros. These are all captured by the elements of
covered.
From this it can be concluded:
- For every prime number
and every natural number
there is, except for isomorphism, exactly one body
with
elements.
- This represents a Galois extension of its prime body.
- The Galois group is cyclic of order
and is
generated by
Other properties of finite bodies:
- All elements except 0 of the additive group of a finite body of characteristic
have order
- As in any finite separable body extension, there is always one primitive element, i.e., an
such that the extension body is obtained by adjunction of only this one element. If
is the minimal polynomial of
then
has degree
and it holds
. Furthermore,
always already the decomposition body of
, i.e.,
decays over
completely into linear factors.
- If is
a divisor of
, then
is a Galois expansion of degree
. The associated Galois group is also cyclic and is generated by the
-th power
of the Frobenius automorphism.
Multiplicative group and discrete logarithm
The multiplicative group (
) of the finite body
consists of all elements of the body except zero. The group operation is the multiplication of the body.
The multiplicative group is a cyclic group with elements. Therefore, since for all elements
this group
holds, each element is a
-th unit root of the body. Those unit roots which are generators of the multiplicative group are called primitive unit roots or primitive roots. These are the φ
distinct zeros of the
-th circular division polynomial. (
denotes the Eulerian φ-function).
If is a primitive root of the multiplicative group
, then the multiplicative group can be
represented as the set Such an
is therefore also called a producer or generator. For each element
there is a uniquely determined number
with
. This number
is called the discrete logarithm of
to the base
. Although
easily computed for any the task of finding
the discrete logarithm
for given to the present knowledge, an extremely computationally expensive operation for large numbers }
. Therefore, the discrete logarithm is used in cryptography, for example in the Diffie-Hellman key exchange.
More examples
The body can be generated using the prime body
can be constructed: Since
is a principal ideal ring, each irreducible element generates a maximal ideal. For an irreducible polynomial
degree
is the factor ring
thus a body with
elements.
The body with 4 elements
For the case an irreducible polynomial of 2nd degree over
sought. Only one exists, namely
. The elements of the body
are the residue classes of the factor ring
.
Let the residue class containing X {\displaystyle X} be
denoted by
null of
in
is. The other zero is then
because it is
The product of is then calculated, for example, as
.
The complete link tables for addition (+) and multiplication (×) in :
|
|
Colored is the lower body .
The body with 49 elements
In the prime body -1 is not a square. This follows from the 1st supplementary theorem to the quadratic reciprocity law of Carl Friedrich Gauss or, for such a small prime, by explicitly squaring all six elements of the multiplicative group. Just as the complex numbers arise from
the real numbers by adjunction of a number
with
too
from
by adjunction of a "number"
with
; formally correct as At the same time,
also a factor ring of the ring of Gaussian integers.
The body with 25 elements
In characteristic 5 -1 is always a square: . However, no squares modulo 5 are the numbers 2 and 3. (In characteristic
with
always exactly half of the elements of the multiplicative group F q ∗
squares and nonsquares, respectively). Thus, the body with 25 elements can be written as
, thus
obtained by adjunction of
About the historical development
That one can calculate with numbers modulo a prime "like with rational numbers", had already been shown by Gauss. Galois introduced imaginary number quantities into the calculation modulo , just like the imaginary unit
in the complex numbers. Thus he was probably the first to consider body extensions of
- even though the abstract notion of bodies was introduced only in 1895 by Heinrich Weber and Frobenius was the first to extend it to finite structures in 1896. Besides or before Eliakim Hastings Moore apparently already studied finite bodies in 1893 and introduced the name Galois field.