Skip to content
Home

Galois field (finite field)

A Galois field, or finite field, is a field with finitely many elements. They exist exactly for orders p^n and are fundamental in algebra, number theory, coding theory and cryptography.

Author: Created: Updated:

Overview

A Galois field, commonly called a finite field, is a set equipped with addition and multiplication satisfying the axioms of a field and containing only finitely many elements. Finite fields arise naturally in abstract algebra and are studied across number theory, algebraic geometry, and applications such as cryptography and coding theory. The standard notation for a finite field is GF(q) or F_q, where q denotes its number of elements.

Image gallery

1 Image
Finite field with 25 elements and base subfield of five elements
en.wikipedia.org · CC0

Basic structure and classification

Every finite field has prime characteristic p, so its size q must be a prime power q = p^n for some integer n ≥ 1. Conversely, for each prime p and positive integer n there exists a field with p^n elements, and any two fields with the same number of elements are isomorphic. The unique (up to isomorphism) field with p elements is often written F_p and is sometimes called the prime field; it can be identified with the integers modulo p.

Construction and important properties

Finite fields of order p^n are constructed as extension fields of F_p. A common construction is to take the polynomial ring F_p[x] and quotient by a degree-n irreducible polynomial f(x), producing F_p[x]/(f(x)). Elements can be represented as polynomials of degree < n with coefficients in F_p, and arithmetic is performed modulo f(x). Several notable properties follow:

  • The multiplicative group of nonzero elements is cyclic of order p^n − 1.
  • The field is an n-dimensional vector space over F_p.
  • The Frobenius map x ↦ x^p is an automorphism; its iterates generate the Galois group of the extension F_{p^n}/F_p.

Examples

Simple examples include GF(2) (the two-element field) and GF(5). Extension examples used in practice include GF(2^8) and GF(256) (another name for GF(2^8) when q = 256) which are widely used in digital systems. Concrete realizations depend on the chosen irreducible polynomial; different polynomials yield isomorphic fields but alternative computational representations.

Applications and significance

Finite fields underpin many practical algorithms and protocols. Reed–Solomon error-correcting codes and QR codes use arithmetic over GF(2^m). Block ciphers and cryptographic primitives often rely on finite-field arithmetic, for example AES uses operations in a byte-oriented field based on GF(2^8). Their algebraic properties also make them central in theoretical topics such as Galois theory and finite geometry.

History and notable facts

The name "Galois field" honors Évariste Galois for foundational work linking field extensions and permutation groups; his ideas led to the study of finite field extensions and their automorphisms. For further reading on background concepts see field (algebra). For broader context and resources consult introductory material in abstract algebra and surveys in number theory and algebraic geometry. Applications are surveyed in texts on coding theory and cryptography. The mathematician honored by the name is Évariste Galois.

Example: The body with 2 elements

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

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

For multiplication applies:

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

Classification of finite bodies

If \mathbb {K} is a finite body, then the kernel of the ring homomorphism {\displaystyle f\colon \mathbb {Z} \to \mathbb {K} }, {\displaystyle n\mapsto n\cdot 1}always of the form p\mathbb {Z} with some prime number p, i.e., it consists of all multiples of p. Note that 1 is not a prime number. This prime pis called the characteristic of \mathbb {K} . According to the homomorphism theorem for rings, the image of fis 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 n-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}

{\displaystyle (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}-4is 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}}-xas 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 pand every natural number nthere 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 nand is {\mathcal {F}}generated by

Other properties of finite bodies:

  • All elements except 0 of the additive group of a finite body of characteristic phave order p.
  • 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 {\displaystyle x,}then fhas degree nand it holds \mathbb {F} _{q}\cong \mathbb {F} _{p}[X]/(f). Furthermore, \mathbb {F} _{q}always already the decomposition body of f, i.e., fdecays over \mathbb {F} _{q}completely into linear factors.
  • If is ma divisor of n, then \mathbb {F} _{p^{m}}\subset \mathbb {F} _{p^{n}}is a Galois expansion of degree n/m. The associated Galois group is also cyclic and is generated by the m-th power {\mathcal {F}}^{m}of the Frobenius automorphism.

Multiplicative group and discrete logarithm

The multiplicative group \mathbb {F} _{q}^{*}( {\displaystyle \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-1elements. Therefore, since for all elements xthis group x^{q-1}=1holds, 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 xa primitive root of the multiplicative group \mathbb {F} _{q}^{*}, then the multiplicative group can be {\displaystyle \left\{x^{0},x^{1},x^{2},\dotsc ,x^{q-2}\right\}}represented as the set Such an xis therefore also called a producer or generator. For each element athere is a uniquely determined number {\displaystyle m\in \{0,1,2,\dotsc ,q-2\}}with a=x^{m}. This number mis called the discrete logarithm of ato the base x. Although x^{m}measily computed for any the task of finding athe discrete logarithm mfor given to the present knowledge, an extremely computationally expensive operation for large numbers }q . 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 {\displaystyle \mathbb {F} _{p}\cong \mathbb {Z} /p\mathbb {Z} }can be constructed: Since {\displaystyle \mathbb {F} _{p}[X]}is a principal ideal ring, each irreducible element generates a maximal ideal. For an irreducible polynomial {\displaystyle f(X)\in \mathbb {F} _{p}[X]}degree nis the factor ring {\displaystyle \mathbb {F} _{p}[X]/(f(X))}thus a body with p^{n}elements.

The body with 4 elements

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

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

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

{\displaystyle 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 {\displaystyle \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 {\displaystyle \mathbb {C} }the real numbers by adjunction of a number \mathrm {i} with {\displaystyle \mathrm {i} ^{2}=-1}too \mathbb {F} _{49}from \mathbb {F} _{7}by adjunction of a "number" jwith {\displaystyle 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 pwith p>2always 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 p, 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.

Related articles

Author

AlegsaOnline.com Galois field (finite field)

URL: https://en.alegsaonline.com/art/37339

Share