Finite body

In the algebra , a branch of mathematics , a finite field or Galois field (after Évariste Galois ) a body with a finite number of elements, d. H. a finite set on which two basic operations understood as addition and multiplication are defined, so that the set, together with these operations, fulfills all requirements of a field.

Finite bodies play an important role in cryptography and coding theory ( forward error correction , for example in the Reed-Solomon code ). In addition, they are fundamental for the study of the prime ideals in the ring of integers of a finite field extension of in the context of algebraic number theory . Compare also branching in the context of extensions of Dedekindring . ${\displaystyle \mathbb {Q} }$

In addition, finite bodies in geometry are important as coordinate areas of finite geometries . They are more general coordinate areas of planes and spaces in synthetic geometry . With the help of addition and multiplication in a finite field, links with weaker algebraic properties are defined. B. make a ternary or quasi-body . Projective and affine planes can then be constructed on these generalized bodies .

The number of elements in a finite field is always a prime power . For every prime number and every positive natural number there is exactly one field with elements (except for isomorphism) , which is denoted by or . is the field of the remainder classes of integers modulo . ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p^{n}}$ ${\displaystyle \mathbb {F} _{p^{n}}}$ ${\displaystyle \operatorname {GF} (p^{n})}$ ${\displaystyle \mathbb {F} _{p}=\operatorname {GF} (p)}$ ${\displaystyle p}$

EH Moore probably coined the English term Galois field in 1893 in honor of Évariste Galois, who had already calculated with certain imaginary numbers modulo . ${\displaystyle p}$

The set of Wedderburn says that multiplication in a finite division ring necessary commutative is. That means that finite oblique bodies are always finite bodies.

Example: The body with 2 elements

The remainder classes modulo 2 form the body with two elements. represent the remainder class of even numbers, the remainder class of odd numbers. The following applies to the addition: ${\displaystyle \mathbb {F} _{2}=\operatorname {GF} (2)}$ ${\displaystyle 0}$ ${\displaystyle 2\mathbb {Z} }$ ${\displaystyle 1}$ ${\displaystyle 1+2\mathbb {Z} }$

${\displaystyle 0+0=0,\qquad 0+1=1,\qquad 1+0=1,\qquad 1+1=0}$

The following applies to the multiplication:

${\displaystyle 0\cdot 0=0\cdot 1=1\cdot 0=0}$ and ${\displaystyle 1\cdot 1=1}$

Classification of finite fields

Is a finite field, then the core of the ring homomorphism , always of the form with a certain prime number , d. i.e., it consists of all multiples of . Note that 1 is not a prime number. This prime number is called the characteristic of . According to the homomorphism theorem for rings, the image of is isomorphic to the remainder class field and is called the prime field of . As a finite extension field there is at the same time a -dimensional vector space over its prime field. Thus has exactly elements. ${\displaystyle \mathbb {K} }$ ${\displaystyle f\colon \mathbb {Z} \to \mathbb {K} }$ ${\displaystyle n\mapsto n\cdot 1}$ ${\displaystyle p\mathbb {Z} }$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \mathbb {K} }$ ${\displaystyle f}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle \mathbb {K} }$ ${\displaystyle \mathbb {K} }$ ${\displaystyle n}$ ${\displaystyle \mathbb {K} }$ ${\displaystyle q=p^{n}}$

In a body with characteristic is due ${\displaystyle \mathbb {K} }$ ${\displaystyle p>0}$ ${\displaystyle {\mathcal {F}}\colon \mathbb {K} \ni x\mapsto x^{p}\in \mathbb {K} }$

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

a homomorphism of additive groups.

The other summands that appear on the right-hand side of the binomial formula are omitted for . bears the name Frobenius homomorphism in honor of Ferdinand Georg Frobenius . The prime body is fixed by point-wise (in fact it is e.g. a multiple of 7). The same is true of every body with elements. On the other hand, the polynomial has at most different zeros of degree . These are all by the elements of detected. ${\displaystyle {\tbinom {p}{i}}\equiv 0{\pmod {p}}}$ ${\displaystyle 1\leq i<p}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle 4^{7}-4}$ ${\displaystyle {\mathcal {F}}^{n}=\mathrm {id} }$ ${\displaystyle q=p^{n}}$ ${\displaystyle x^{p^{n}}-x}$ ${\displaystyle p^{n}}$ ${\displaystyle p^{n}}$ ${\displaystyle \mathbb {K} }$

From this it can be concluded:

• For every prime number and every natural number there is exactly one field with elements except for isomorphism . ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q=p^{n}}$
• This represents a Galois extension of its prime field.
• The Galois group is cyclic of order and is generated by. ${\displaystyle n}$ ${\displaystyle {\mathcal {F}}}$

Further properties of finite bodies:

• All elements except 0 of the additive group of a finite field of the characteristic have order ${\displaystyle p}$ ${\displaystyle p.}$
• As with any finite separable extension of fields there is always a primitive element , so a such that the expansion body by adjunction only this creates an element. If the minimal polynomial of , then has degree and it holds . Furthermore, the disintegration body of , i.e. This means that it already completely breaks down into linear factors. ${\displaystyle x\in \mathbb {F} _{q}}$ ${\displaystyle f\in \mathbb {F} _{p}[X]}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{q}\cong \mathbb {F} _{p}[X]/(f)}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \mathbb {F} _{q}}$
• 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 homomorphism. ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{p^{m}}\subset \mathbb {F} _{p^{n}}}$ ${\displaystyle n/m}$ ${\displaystyle m}$ ${\displaystyle {\mathcal {F}}^{m}}$

Multiplicative group and discrete logarithm

The multiplicative group of the finite field consists of all elements of the field with the exception of zero. The group operation is the multiplication of the body. ${\displaystyle \mathbb {F} _{q}^{*}}$ ${\displaystyle \mathbb {F} _{q}}$

The multiplicative group is a cyclic group with elements. Since, therefore, applies to all elements of this group , each element is a -th root of unity of the body. Those roots of unity that are producers of the multiplicative group are called primitive roots of unity or primitive roots. These are the different zeros of the -th circle division polynomial . ( denotes Euler's φ function .) ${\displaystyle q-1}$ ${\displaystyle x}$ ${\displaystyle x^{q-1}=1}$ ${\displaystyle (q-1)}$ ${\displaystyle \varphi (q-1)}$ ${\displaystyle (q-1)}$ ${\displaystyle \varphi }$

If the multiplicative group is a primitive root , then the multiplicative group can be represented as a set . This is therefore also referred to as a generator or generator. For each element there is a unique number with . This number is called the discrete logarithm from to the base . Although it can be calculated without any problems for each , the task of finding the discrete logarithm for a given is, according to the current state of knowledge, an extremely computationally intensive process for large numbers . This is why the discrete logarithm is used in cryptography , for example in Diffie-Hellman key exchange . ${\displaystyle x}$ ${\displaystyle \mathbb {F} _{q}^{*}}$ ${\displaystyle \left\{x^{0},x^{1},x^{2},\dotsc ,x^{q-2}\right\}}$ ${\displaystyle x}$ ${\displaystyle a}$ ${\displaystyle m\in \{0,1,2,\dotsc ,q-2\}}$ ${\displaystyle a=x^{m}}$ ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle x}$ ${\displaystyle x^{m}}$ ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle q}$

Further examples

The field can be constructed with the help of the prime field : Since there is a main ideal ring, every irreducible element creates a maximal ideal. For an irreducible polynomial of degree the factor ring is thus a field with elements. ${\displaystyle \mathbb {F} _{p^{n}}}$ ${\displaystyle \mathbb {F} _{p}\cong \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle \mathbb {F} _{p}[X]}$ ${\displaystyle f(X)\in \mathbb {F} _{p}[X]}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{p}[X]/(f(X))}$ ${\displaystyle p^{n}}$

The body with 4 elements

For this case , an irreducible polynomial of the 2nd degree is searched for. There is only one, namely . The elements of the body are the remainder classes of the factor ring . The polynomials of degree less than 2, i.e . ,, and , can be chosen as representatives. For easier notation, the body elements are identified with their representatives. For example, the product of then is calculated as ${\displaystyle p^{n}=2^{2}}$ ${\displaystyle \mathbb {F} _{2}}$ ${\displaystyle X^{2}+X+1}$ ${\displaystyle \mathbb {F} _{4}}$ ${\displaystyle \mathbb {F} _{2}[X]/(X^{2}+X+1)}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle X}$ ${\displaystyle X+1}$ ${\displaystyle X,X+1\in \mathbb {F} _{4}}$

${\displaystyle X\cdot (X+1)=X^{2}+X=1+X^{2}+X+1=1{\pmod {X^{2}+X+1}}}$.

The complete link tables for addition and multiplication are in ${\displaystyle \mathbb {F} _{4}}$

${\displaystyle +}$ 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

${\displaystyle \cdot }$ 0 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

The body with 49 elements

In the prime field , -1 is not a square. This follows from the 1st supplementary sentence to the quadratic reciprocity law by Carl Friedrich Gauß or - with such a small prime number - by explicitly squaring all six elements of the multiplicative group. Just as the complex numbers from the real numbers by adjoining a number with arise can also be made by adjoining a "number" with win; formally correct as Simultaneously is also a factor ring of the ring of whole Gaussian numbers . ${\displaystyle \mathbb {F} _{7}\cong \mathbb {Z} /7\mathbb {Z} }$ ${\displaystyle \mathbb {C} }$ ${\displaystyle \mathrm {i} }$ ${\displaystyle \mathrm {i} ^{2}=-1}$ ${\displaystyle \mathbb {F} _{49}}$ ${\displaystyle \mathbb {F} _{7}}$ ${\displaystyle j}$ ${\displaystyle j^{2}=-1=6}$ ${\displaystyle \mathbb {F} _{49}\cong \mathbb {F} _{7}[X]/(X^{2}+1).}$ ${\displaystyle \mathbb {F} _{49}\cong \mathbb {Z} [\,\mathrm {i} \,]/(7)}$

The body with 25 elements

In characteristic 5 is -1 always a square: . However, the numbers 2 and 3 are not squares modulo 5 (in characteristic with , exactly half of the elements of the multiplicative group are always squares or non-squares.) The field with 25 elements can thus be obtained as , i.e. by the adjunction of . ${\displaystyle 2^{2}\equiv -1{\pmod {5}}}$ ${\displaystyle p}$ ${\displaystyle p>2}$ ${\displaystyle \mathbb {F} _{q}^{*}}$ ${\displaystyle \mathbb {F} _{5}[X]/(X^{2}-2)}$ ${\displaystyle {\sqrt {2}}}$

To the historical development

Gauss had already shown that one can calculate with numbers modulo a prime number “like with rational numbers”. Galois introduced modulo imaginary number quantities into the calculation , just like the imaginary unit in complex numbers. He was probably the first to consider the body extension of - even if the abstract concept of the body was first introduced by Heinrich Weber in 1895 and Frobenius was the first to extend it to finite structures in 1896. In addition or before, Eliakim Hastings Moore had already studied finite bodies in 1893 and introduced the name Galois field . ${\displaystyle p}$ ${\displaystyle \mathrm {i} }$ ${\displaystyle \mathbb {F} _{p}}$

literature

• Dieter Jungnickel: Finite fields: Structure and arithmetics. BI Wissenschaftsverlag, 1993, ISBN 3-411-16111-6 .
• Hans Kurzweil: Finite Bodies. Understand, calculate, apply. Springer, ISBN 978-3-540-795971 .

On the historical development:

• Hans Wußing : 6000 years of mathematics. Vol. 1. Springer, Berlin 2008. ISBN 978-3-540-77189-0 .

Footnotes and individual references

1. ↑ On the historical development cf. man Wussing, p. 354 ff.
2. ↑ See Earliest Known Uses of Some of the Words of Mathematics (F). Retrieved September 12, 2009.