Finite field

(Redirected from Galois field)

In algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains a finite number of elements, called its order (the size of the underlying set). As with any field, a finite field is a set on which the operations of commutative multiplication, addition, subtraction and division (by anything except zero) have been defined. Common, but not the only, examples of finite fields are given by the integers modulo a prime, that is, the integers mod n where n is a prime number, such as Z/2Z or Z/7Z.

Finite fields only exist when the order (size) is a prime power pk (where p is a prime number and k is a positive integer). For each prime power, there is a finite field with this size, and all fields of a given order are isomorphic. The characteristic of a field of order pk is p (this means that adding p copies of any element always results in zero). Z/2Z (the integers mod 2) has characteristic 2 since, as $1 + 1 \equiv 0 \pmod 2$, we have $1+1=0$ in this field. Similarly, Z/5Z has characteristic 5 since $0 = 1 + 1 + 1 + 1 + 1 = 2 + 2 + 2 + 2 + 2 = \cdots = 4 + 4 + 4 + 4 + 4$ in this field.

In a finite field of order q, the polynomial XqX has all the elements of the finite field as roots, and so, is the product of q different linear factors. Just considering multiplication, the non-zero elements of any finite field form a multiplicative group that is a cyclic group. Therefore, the non-zero elements can be expressed as the powers of a single element called a primitive element of the field (in general there will be several primitive elements for a given field.)

A field has, by definition, a commutative multiplication operation. A more general algebraic structure that satisfies all the other axioms of a field but isn't required to have a commutative multiplication is called a division ring (or sometimes skewfield). A finite division ring is a finite field by Wedderburn's little theorem. This result shows that the finiteness condition in the definition of a finite field can have algebraic consequences.

Finite fields are fundamental in a number of areas of mathematics and computer science, including number theory, algebraic geometry, Galois theory, finite geometry, cryptography and coding theory.

Basic properties

The integers modulo p form a finite field if and only if p is a prime number. It is the prime field of characteristic p, and is denoted Z/pZ, $\mathbb{F}_{p}$, Fp or GF(p).

Let F be a finite field. For any element x in F and any integer n, let us denote by nx the sum of n copies of x. The least positive n such that n⋅1 = 0 must exist and is prime; it is called the characteristic of the field.

A field of characteristic 2 is also called a binary field. The number of elements of a finite field is called its order or its size.

If the characteristic of F is p, the operation $(n,x)\mapsto n\cdot x$ makes F a GF(p)-vector field. It follows that the number of elements of F is pn, where p, the characteristic, is a prime number, and n is the dimension of F as GF(p)-vector field.

For every prime number p and every positive integer n, there are finite fields of order pn, and all these fields are isomorphic (see below). One may therefore identify all fields of order pn, which are therefore denoted $\mathbb{F}_{p^n}$, Fpn or GF(pn), where the letters GF stand for "Galois field".[1]

The identity

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

is true (for every x and y) in a field of characteristic p. (This follows from the fact that all, except the first and the last, binomial coefficients of the expansion of $(x+y)^p$ are multiples of p).

For every element x in the prime field GF(p), one has xp = x (This is an immediate consequence of Fermat's little theorem, and this may be easily proved as follows: the equality is trivially true for x = 0 and x = 1; one obtains the result for the other elements of GF(p) by applying the above identity to x and 1, where x successively takes the values 1, 2, ..., p−1 modulo p). This implies the equality

$X^p-X=\prod_{a\in {\rm GF}(p)} (X-a)$

for polynomials over GF(p).

Existence and uniqueness

Let q = pn be a prime power, and F be the splitting field of the polynomial

$P=X^q-X$

over the prime field GF(p). This means that F is a finite field of lowest order, in which P has q distinct roots (the roots are distinct, as the formal derivative of F is equal to 1). Above identity shows that the sum and the product of two roots of P are roots of P, as well as the multiplicative inverse of a root of P. In other word, the roots of P form a field of order q, which is equal to F by the minimality of the splitting field.

The uniqueness up to isomorphism of splitting fields implies thus that all fields of order q are isomorphic.

In summary, we have the following classification theorem first proved in 1893 by E. H. Moore. [2]

The order of a finite field is a prime power. For every prime power q there are fields of order q, and they are all isomorphic. In these fields, every element satisfies

$x^q=x,$

and the polynomial $X^q-X$ factors as

$X^q-X= \prod_{a\in F} (X-a).$

It follows that GF(pn) contains a subfield isomorphic to GF(pm) if and only m is a divisor of n; in that case, this subfield is unique. In fact, the polynomial $X^{p^m}-X$ divides $X^{p^n}-X$ if and only if m is a divisor of n.

Polynomial factorization

If F is a finite field, a non-constant monic polynomial with coefficients in F is irreducible over F, if it is not the product of two non-constant monic polynomials, with coefficients in F.

As every polynomial ring over a field is a unique factorization domain, every monic polynomial over a finite field may be factored in a unique way (up to the order of the factors) into a product of irreducible monic polynomials.

There are efficient algorithms for testing polynomial irreducibility and factoring polynomials over finite field. They are a key step for factoring polynomials over the integers or the rational numbers. At least for this reason, every computer algebra system has functions for factoring polynomials over finite fields, or, at least, over finite prime fields.

Irreducible polynomials of a given degree

The polynomial

$X^q-X$

factors into linear factors over a field of order q. More precisely, this polynomial is the product of all monic polynomials of degree one over a field of order q.

This implies that, if q = pn that Xq - X is the product of all monic irreducible polynomials over GF(p), whose degree divides n

This property is used to compute the product of the irreducible factors of each degree of polynomials over GF(p); see Distinct degree factorization.

Number of monic irreducible polynomials of a given degree over a finite field

The number N(q,n of monic irreducible polynomials of degree n over GF(q) is given by[3]

$N(q,n)=\frac{1}{n}\sum_{d|n} \mu(d)q^{\frac{n}{d}},$

where μ is the Möbius function. This formula is almost a direct consequence of above property of Xq - X.

By the above formula, the number of irreducible (not necessarily monic) polynomials of degree n over GF(q) is (q − 1)N(q, n).

A (slightly simpler) lower bound for N(q, n) is

$N(q,n)\geq\frac{1}{n} \left(q^n-\sum_{p|n, \ p \text{ prime}} q^{\frac{n}{p}}\right).$

One may easily deduce that, for every q and every n, there is at least one irreducible polynomial of degree n over GF(q). This lower bound is sharp for q = n = 2.

Explicit construction of finite fields

Prime fields

The prime field GF(p) of order and characteristic p is easily constructed as the integers modulo p.

Thus, the elements are represented by integers in the range 0, ..., p − 1. The sum, the difference and the product are computed by taking the remainder by p of the integer result. The multiplicative inverse of an element may be computed by using the extended Euclidean algorithm (see Extended Euclidean algorithm § Modular integers).

Non-prime field

Given a prime power q = pn with p and n > 1, the field GF(q) may be explicitly constructed in the following way. One chooses first an irreducible polynomial P in GF(p)[X] (such an irreducible polynomial always exists). Then the quotient ring

${\rm GF}(q) = {\rm GF}(p)[X]/(P)$

of the polynomial ring GF(p)[X] by the ideal generated by P is a field of order q.

More explicitly, the elements of GF(q) are the polynomials over GF(p), whose degree is at most n. The addition and the subtraction are those of polynomials over GF(p). The product of two elements is the remainder of the Euclidean division by P of the product in GF(p)[X]. The multiplicative inverse of a non-zero element may be computed with the extended Euclidean algorithm; see Extended Euclidean algorithm § Simple algebraic field extensions.

Except in the construction of GF(4), there are several possible choices for P, which produce isomorphic results. To simplify the Euclidean division, for P one commonly chooses polynomials of the form

$X^n+aX+b,$

which make the needed Euclidean divisions very efficient.

In the next sections, we will show how this general construction method works for small finite fields.

Field with four elements

Over GF(2), there is only irreducible polynomial of degree 2:

$X^2+X+1$

Therefore, for GF(4) the construction of the preceding section must involve this polynomial, and

${\rm GF}(4) = {\rm GF}(2)/(X^2+X+1).$

If one denotes a a root of this polynomial in GF(4), the tables of the operations in GF(4) are (for the third table, x must be read on the top, and y on the left)

+ 0 1 a 1+a
0 0 1 a 1+a
1 1 0 1+a a
a a 1+a 0 1
1+a 1+a a 1 0
× 0 1 a 1+a
0 0 0 0 0
1 0 1 a 1+a
a 0 a 1+a 1
1+a 0 1+a 1 a
x/y 0 1 a 1+a
1 0 1 a 1+a
a 0 1+a 1 a
1+a 0 a 1+a 1

GF(p2) for an odd prime p

For applying above general construction of finite fields in the case of GF(p2), one has to find an irreducible polynomial of degree 2. For p = 2, this has been done in the preceding section. If p is an odd prime, there are always irreducible polynomials of the form X2r, with r in GF(p).

More precisely, the polynomial X2r is irreducible over GF(p) if and only if r is a quadratic non-residue modulo p (this is almost the definition of a quadratic non-residue). There are $\frac{p-1}{2}$ quadratic non-residues modulo p. For example, 2 is a quadratic non-residue for p = 3, 5, 11, 13, ..., and 3 is a quadratic non-residue for p = 5, 7, 17, .... If p ≡ 3 mod 4, that is p = 3, 7, 11, 19, ..., one may choose −1 ≡ p − 1 as a quadratic non-residue, which allows us to have a very simple irreducible polynomial X2 + 1.

Having chosen a quadratic non-residue r, let $\alpha$ be a symbolic square root of r, that is a symbol which has the property $\alpha^2=r,$, in the same way as the complex number i is a symbolic square root of −1. Then, the elements of GF(p2) are all the linear expressions

$a+b\alpha,$

with a and b in GF(p). The operations on GF(p2) are defined as follows (the operations between elements of GF(p) represented by Latin letters are the operations in GF(p)):

\begin{align} -(a+b\alpha)&=-a+(-b)\alpha\\ (a+b\alpha)+(c+d\alpha)&=(a+c)+(b+d)\alpha\\ (a+b\alpha)(c+d\alpha)&=(ab + rcd)+ (ad+bc)\alpha\\ (a+b\alpha)^{-1}&=a(a^2-rb^2)^{-1}+(-b)(a^2-rb^2)^{-1}\alpha \end{align}

GF(8) and GF(27)

The polynomial

$X^3-X-1$

is irreducible over GF(2) and GF(3), that is, it is irreducible modulo 2 and 3 (to show this it suffice to show that it has no root in GF(2) nor in GF(3)). It follows that the elements of GF(8) and GF(27) may be represented by expressions

$a+b\alpha+c\alpha^2,$

where a, b, c are elements of GF(2) or GF(3) (respectively), and $\alpha$ is a symbol such that

$\alpha^3=\alpha+1.$

The addition, additive inverse and multiplication on GF(8) and GF(27) may thus be defined as follows; in following formulas, the operations between elements of GF(2) or GF(3), represented by Latin letters are the operations in GF(2) or GF(3), respectively:

\begin{align} -(a+b\alpha+c\alpha^2)&=-a+(-b)\alpha+(-c)\alpha^2 \qquad\text{(For } GF(2), \text{this operation is the identity)}\\ (a+b\alpha+c\alpha^2)+(d+e\alpha+f\alpha^2)&=(a+d)+(b+e)\alpha+(c+f)\alpha^2\\ (a+b\alpha+c\alpha^2)(d+e\alpha+f\alpha^2)&=(ad + bf+cd)+ (ae+bd+bf+cd+cf)\alpha+(af+be+cd+cf)\alpha^2 \end{align}

GF(16}

The polynomial

$X^4+X+1$

is irreducible over GF(2), that is, it is irreducible modulo 2. It follows that the elements of GF(16)may be represented by expressions

$a+b\alpha+c\alpha^2+d\alpha^3,$

where a, b, c,d are either 0 or 1 (elements of GF(2)), and $\alpha$ is a symbol such that

$\alpha^4=\alpha+1.$

As the characteristic of GF(2) is 2, each element is its additive inverse in GF(16}. The addition and multiplication on GF(16) may be defined as follows; in following formulas, the operations between elements of GF(2) or GF(3), represented by Latin letters are the operations in GF(2) or GF(3), respectively:

\begin{align} (a+b\alpha+c\alpha^2+d\alpha^3)+(e+f\alpha+g\alpha^2+h\alpha^3)&=(a+e)+(b+f)\alpha+(c+g)\alpha^2+(d+h)\alpha^3\\ (a+b\alpha+c\alpha^2+d\alpha^3)+(e+f\alpha+g\alpha^2+h\alpha^3)&=(ae+bh+cg+df) + (af+be+bh+cg+df +ch+dg)\alpha +(ag+bf+ce +ch+dg+dh)\alpha^2 +(ah+bg+cf+de +dg)\alpha^3 \end{align}

Multiplicative structure

In what follows F is a finite field with q elements, and F× = F\{0}.

Cyclic

The multiplicative group of every finite field is cyclic, a special case of a theorem mentioned in Fields. A generator for F× is called a primitive element, i.e. there exists an element x in F such that

F = {0, 1, x, x2, ..., xq−2}.

Unless q = 2, 3, the primitive element x is not unique. The set of generators has size φ(q − 1) where φ is Euler's totient function. If we fix a generator, then for any non-zero element a in F, there is a unique integer n with 0 ≤ nq − 2 such that

a = xn.

For a given a, n is called the discrete log of a in F, to the base x.

Analog of Fermat's little theorem

Theorem. Every element of a finite field of size q satisfies aq = a.

Proof: Since F× is a multiplicative group of order q − 1, Lagrange's theorem implies that aq−1 = 1 for all aF×. Hence aq = a for all aF×. This also holds for 0, and hence for all aF.

Remark. When q is prime, this is just Fermat's little theorem, which states that apa (mod p) for any integer a and prime p.

Roots of unity

Let n > 0 be an integer, a n-th root of unity in F is a solution of the equation xn = 1, a n-th primitive root of unity is a solution of the equation xn = 1 that is not a solution of the equation xm = 1 for any positive integer m < n.

Unlike the n-th roots of unity in C, the number of n-th roots of unity in F is not n, it is equal to gcd(n, q − 1). Thus if nq − 1 then F has no primitive n-roots of unity, while if n | q − 1 then the number of primitive n-th roots of unity in F is φ(n).

Frobenius automorphism and Galois theory

In this section, p is a prime number, and q = pn is a power of p.

In GF(q), the identity $(x+y)^p=x^p+y^p$ implies that the map

$\varphi:x \mapsto x^p$

is a GF(p)-linear endomorphism and a field automorphism of GF(q), which fixes every element of the subfield GF(p). It is called the Frobenius automorphism, after Ferdinand Georg Frobenius.

Denoting by $\varphi^k$ the composition of $\varphi$ with itself, k times, we have

$\varphi^k:x \mapsto x^{p^k}.$

It has been shown in the preceding section that $\varphi^n$ is the identity. For 0 < k < n, the automorphism $\varphi^k$ is not the identity, as, otherwise, the polynomial

$X^{p^k}-X$

would have more than pk roots.

There are no other GF(p)-automorphisms of GF(q). In other words, GF(pn) has exactly n GF(p)-automorphisms, which are

$\mathrm{Id}=\varphi^0, \varphi, \varphi^2, \ldots, \varphi^{n-1}.$

In terms of Galois theory, this means that GF(pn) is a Galois extension of GF(p), which has a cyclic Galois group.

The fact that the Frobenius map is surjective implies that every finite field is perfect.

Applications

Discrete exponentiation, also known as calculating a = xn from x and n, can be computed quickly using techniques of fast exponentiation such as binary exponentiation, which takes only O(log n) field operations. No fast way of computing the discrete logarithm n given a and x is known, and this has many applications in cryptography, such as the Diffie–Hellman protocol.

Finite fields also find applications in coding theory: many codes are constructed as subspaces of vector spaces over finite fields.

Within number theory, the significance of finite fields is their role in the definition of the Frobenius element (or, more accurately, Frobenius conjugacy class) attached to a prime ideal in a Galois extension of number fields, which in turn is needed to understand Artin L-functions of representations of the Galois group, the non-abelian generalization of Dirichlet L-functions.

Counting solutions to equations over finite fields leads into deep questions in algebraic geometry, the Weil conjectures, and in fact was the motivation for Grothendieck's development of modern algebraic geometry.

Extensions

Algebraic closure

A finite field F can not be algebraically closed.

Consider the polynomial:

$f(T)=1+\prod_{\alpha \in \mathbf{F}} (T-\alpha)$

f has no roots over F, as f (α) = 1 for all α in F.

The direct limit of the system:

{Fp, Fp2, ..., Fpn, ...},

with inclusion, is an infinite field. It is the algebraic closure of all the fields in the system, and is denoted by: $\overline{\mathbf{F}_p}$.

The inclusions commute with the Frobenius map, as it is defined the same way on each field (xx p), so the Frobenius map defines an automorphism of $\overline{\mathbf{F}_p}$, which carries all subfields back to themselves. In fact Fpn can be recovered as the fixed points of the n-th iterate of the Frobenius map.

However unlike the case of finite fields, the Frobenius automorphism on $\overline{\mathbf{F}_p}$ has infinite order, and it does not generate the full group of automorphisms of this field. That is, there are automorphisms of $\overline{\mathbf{F}_p}$ which are not a power of the Frobenius map. However, the group generated by the Frobenius map is a dense subgroup of the automorphism group in the Krull topology. Algebraically, this corresponds to the additive group Z being dense in the profinite integers (direct product of the p-adic integers over all primes p, with the product topology).

If we actually construct our finite fields in such a fashion that Fpn is contained in Fpm whenever n divides m, then this direct limit can be constructed as the union of all these fields. Even if we do not construct our fields this way, we can still speak of the algebraic closure, but some more delicacy is required in its construction.

Wedderburn's little theorem

A division ring is a generalization of field. Division rings are not assumed to be commutative. There are no non-commutative finite division rings: Wedderburn's little theorem states that all finite division rings are commutative, hence finite fields. The result holds even if we relax associativity and consider alternative rings, by the Artin–Zorn theorem.