Finite field

Author: Leandro Alegsa

29-06-2021 22:26

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 $\mathbb {Q}$ 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 $p^{n}$ elements, which is denoted by $\mathbb {F} _{p^{n}}$ or $\operatorname {GF} (p^{n})$ is denoted. $\mathbb {F} _{p}=\operatorname {GF} (p)$ 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 $\mathbb {F} _{2}=\operatorname {GF} (2)$ with two elements. $0$ represent the residue class $2\mathbb {Z}$ of even numbers, class $1+2\mathbb {Z}$ of the odd numbers. For addition holds:

$0+0=0,\qquad 0+1=1,\qquad 1+0=1,\qquad 1+1=0$

For multiplication applies:

$0\cdot 0=0\cdot 1=1\cdot 0=0$ and $1\cdot 1=1$

Classification of finite bodies

If $\mathbb {K}$ is a finite body, then the kernel of the ring homomorphism $f\colon \mathbb {Z} \to \mathbb {K}$ , $n\mapsto n\cdot 1$ always of the form $p\mathbb {Z}$ 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 $\mathbb {K}$ . According to the homomorphism theorem for rings, the image of is isomorphic to the residue class body $\mathbb {Z} /p\mathbb {Z}$ and is called the prime body of $\mathbb {K}$ . As a finite extension body, $\mathbb {K}$ also an -dimensional vector space over its prime body. Thus $\mathbb {K}$ exactly $q=p^{n}$ elements.

In a body $\mathbb {K}$ with characteristic p>0 : K because of ${\mathcal {F}}\colon \mathbb {K} \ni x\mapsto x^{p}\in \mathbb {K}$

$(x+y)^{p}=x^{p}+y^{p}$

a homomorphism of additive groups.

The remaining summands occurring on the right-hand side according to the binomial formula drop because of ${\tbinom {p}{i}}\equiv 0{\pmod {p}}$ for ${\mathcal {F}}$ homorphism in honor of Ferdinand Georg Frobenius, which is an automorphism and therefore also called Frobenius automorphism. The prime body is pointwise fixed by ${\mathcal {F}}$ (in fact, for example, $4^{7}-4$ is a multiple of 7). Similarly, ${\mathcal {F}}^{n}=\mathrm {id}$ on any body with $q=p^{n}$ elements. On the other hand, $x^{p^{n}}-x$ as a polynomial of degree $p^{n}$ at most $p^{n}$ distinct zeros. These are all captured by the elements of $\mathbb {K}$ covered.

From this it can be concluded:

For every prime number and every natural number there is, except for isomorphism, exactly one body $\mathbb {F} _{q}$ with $q=p^{n}$ elements.
This represents a Galois extension of its prime body.
The Galois group is cyclic of order and is ${\mathcal {F}}$ 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 $x\in \mathbb {F} _{q}$ such that the extension body is obtained by adjunction of only this one element. If $f\in \mathbb {F} _{p}[X]$ is the minimal polynomial of $x,$ then has degree and it holds $\mathbb {F} _{q}\cong \mathbb {F} _{p}[X]/(f)$ . Furthermore, $\mathbb {F} _{q}$ always already the decomposition body of , i.e., decays over $\mathbb {F} _{q}$ completely into linear factors.
If is a divisor of , then $\mathbb {F} _{p^{m}}\subset \mathbb {F} _{p^{n}}$ is a Galois expansion of degree . The associated Galois group is also cyclic and is generated by the -th power ${\mathcal {F}}^{m}$ of the Frobenius automorphism.

Multiplicative group and discrete logarithm

The multiplicative group $\mathbb {F} _{q}^{*}$ ( $\mathbb {F} _{q}^{\times }$ ) of the finite body $\mathbb {F} _{q}$ 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 q-1 elements. Therefore, since for all elements this group $x^{q-1}=1$ holds, each element is a (q-1) -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 φ $\varphi (q-1)$ distinct zeros of the (q-1) -th circular division polynomial. ( $\varphi$ denotes the Eulerian φ-function).

If is a primitive root of the multiplicative group $\mathbb {F} _{q}^{*}$ , then the multiplicative group can be $\left\{x^{0},x^{1},x^{2},\dotsc ,x^{q-2}\right\}$ represented as the set Such an is therefore also called a producer or generator. For each element there is a uniquely determined number $m\in \{0,1,2,\dotsc ,q-2\}$ with $a=x^{m}$ . This number is called the discrete logarithm of to the base . Although $x^{m}$ 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 ${\mathbb {F}}_{{p^{n}}}$ can be generated using the prime body $\mathbb {F} _{p}\cong \mathbb {Z} /p\mathbb {Z}$ can be constructed: Since $\mathbb {F} _{p}[X]$ is a principal ideal ring, each irreducible element generates a maximal ideal. For an irreducible polynomial $f(X)\in \mathbb {F} _{p}[X]$ degree is the factor ring $\mathbb {F} _{p}[X]/(f(X))$ thus a body with $p^{n}$ elements.

The body with 4 elements

For the case $p^{n}=2^{2}$ an irreducible polynomial of 2nd degree over $\mathbb {F} _{2}$ sought. Only one exists, namely $f(X)=X^{2}+X+1$ . The elements of the body $\mathbb {F} _{4}$ are the residue classes of the factor ring $\mathbb {F} _{2}[X]/(f(X))$ . Let the residue class containing X {\displaystyle X} be denoted by null of f(X) in $\mathbb {F} _{2}[X]$ is. The other zero is then $x+1,$ because it is

$(x+1)^{2}+(x+1)+1=x^{2}+2x+1+x+1+1=x^{2}+x+1=f(x)=0.$

The product of $x,x+1\in \mathbb {F} _{4}$ is then calculated, for example, as

$x\times (x+1)=x^{2}+x=1+x^{2}+x+1=1+f(x)=1$ .

The complete link tables for addition (+) and multiplication (×) in $\mathbb {F} _{4}$ :

+	0	1	x	x+1
0	0	1	x	x+1
1	1	0	x+1	x
x	x	x+1	0	1
x+1	x+1	x	1	0

×	000	1	x	x+1
0	0	0	0	0
1	0	1	x	x+1
x	0	x	x+1	1
x+1	0	x+1	1	x

Colored is the lower body $\mathbb {F} _{2}$ .

The body with 49 elements

In the prime body $\mathbb {F} _{7}\cong \mathbb {Z} /7\mathbb {Z}$ -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 $\mathbb {C}$ the real numbers by adjunction of a number $\mathrm {i}$ with $\mathrm {i} ^{2}=-1$ too $\mathbb {F} _{49}$ from $\mathbb {F} _{7}$ by adjunction of a "number" with $j^{2}=-1=6$ ; formally correct as At the same time, $\mathbb {F} _{49}\cong \mathbb {F} _{7}[X]/(X^{2}+1).$ $\mathbb {F} _{49}\cong \mathbb {Z} [\,\mathrm {i} \,]/(7)$ also a factor ring of the ring of Gaussian integers.

The body with 25 elements

In characteristic 5 -1 is always a square: $2^{2}\equiv -1{\pmod {5}}$ . However, no squares modulo 5 are the numbers 2 and 3. (In characteristic with p>2 always exactly half of the elements of the multiplicative group F q ∗ $\mathbb {F} _{q}^{*}$ squares and nonsquares, respectively). Thus, the body with 25 elements can be written as $\mathbb {F} _{5}[X]/(X^{2}-2)$ , thus ${\sqrt {2}}$ 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 $\mathrm {i}$ in the complex numbers. Thus he was probably the first to consider body extensions of $\mathbb {F} _{p}$ - 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.

Search within the encyclopedia