Finite field

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

${\displaystyle {\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 strictly less than 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

${\displaystyle X^{n}+aX+b,}$

which make the needed Euclidean divisions very efficient. However, for some fields, typically in characteristic 2, irreducible polynomials of the form Xⁿ + aX + b may not exist. In characteristic 2, if the polynomial Xⁿ + X + 1 is reducible, it is recommended to choose Xⁿ + X^k + 1 with the lowest possible k that makes the polynomial irreducible. If all these trinomials are reducible, one chooses "pentanomials" Xⁿ + X^a + X^b + X^c + 1, as polynomials of degree greater than 1, with an even number of terms, are never irreducible in characteristic 2, having 1 as a root.[3]

A possible choice for such a polynomial is given by Conway polynomials. They ensure a certain compatibility between the representation of a field and the representations of its subfields.

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

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

${\displaystyle X^{2}+X+1}$

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

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

If one denotes α a root of this polynomial in GF(4), the tables of the operations in GF(4) are the following. There is no table for subtraction, because subtraction is identical to addition, as is the case for every field of characteristic 2. In the third table, for the division of x by y, x must be read on the left, and y on the top.

For applying the above general construction of finite fields in the case of GF(p²), 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 X² − r, with r in GF(p).

More precisely, the polynomial X² − r 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 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 X² + 1.

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

${\displaystyle a+b\alpha ,}$

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

${\displaystyle {\begin{aligned}-(a+b\alpha )&=-a+(-b)\alpha \\(a+b\alpha )+(c+d\alpha )&=(a+c)+(b+d)\alpha \\(a+b\alpha )(c+d\alpha )&=(ac+rbd)+(ad+bc)\alpha \\(a+b\alpha )^{-1}&=a(a^{2}-rb^{2})^{-1}+(-b)(a^{2}-rb^{2})^{-1}\alpha \end{aligned}}}$

The polynomial

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

${\displaystyle a+b\alpha +c\alpha ^{2},}$

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

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

${\displaystyle {\begin{aligned}-(a+b\alpha +c\alpha ^{2})&=-a+(-b)\alpha +(-c)\alpha ^{2}\qquad {\text{(for }}\mathrm {GF} (8),{\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+ce)+(ae+bd+bf+ce+cf)\alpha +(af+be+cd+cf)\alpha ^{2}\end{aligned}}}$

The polynomial

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

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

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

${\displaystyle \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), represented by Latin letters are the operations in GF(2).

${\displaystyle {\begin{aligned}(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 \;+\\&\quad \;(ag+bf+ce+ch+dg+dh)\alpha ^{2}+(ah+bg+cf+de+dh)\alpha ^{3}\end{aligned}}}$

If a is a primitive element in GF(q), then for any non-zero element x in F, there is a unique integer n with 0 ≤ n ≤ q − 2 such that

x = aⁿ.

This integer n is called the discrete logarithm of x to the base a.

While aⁿ can be computed very quickly, for example using exponentiation by squaring, there is no known efficient algorithm for computing the inverse operation, the discrete logarithm. This has been used in various cryptographic protocols, see Discrete logarithm for details.

When the nonzero elements of GF(q) are represented by their discrete logarithms, multiplication and division are easy, as they reduce to addition and subtraction modulo q – 1. However, addition amounts to computing the discrete logarithm of a^m + aⁿ. The identity

a^m + aⁿ = aⁿ(a^m−n + 1)

allows one to solve this problem by constructing the table of the discrete logarithms of aⁿ + 1, called Zech's logarithms, for n = 0, ..., q − 2 (it is convenient to define the discrete logarithm of zero as being −∞).

Zech's logarithms are useful for large computations, such as linear algebra over medium-sized fields, that is, fields that are sufficiently large for making natural algorithms inefficient, but not too large, as one has to pre-compute a table of the same size as the order of the field.

Every nonzero element of a finite field is a root of unity, as x^q−1 = 1 for every nonzero element of GF(q).

If n is a positive integer, an nth primitive root of unity is a solution of the equation xⁿ = 1 that is not a solution of the equation x^m = 1 for any positive integer m < n. If a is a nth primitive root of unity in a field F, then F contains all the n roots of unity, which are 1, a, a², ..., aⁿ⁻¹.

The field GF(q) contains a nth primitive root of unity if and only if n is a divisor of q − 1; if n is a divisor of q − 1, then the number of primitive nth roots of unity in GF(q) is φ(n) (Euler's totient function). The number of nth roots of unity in GF(q) is gcd(n, q − 1).

In a field of characteristic p, every (np)th root of unity is also a nth root of unity. It follows that primitive (np)th roots of unity never exist in a field of characteristic p.

On the other hand, if n is coprime to p, the roots of the nth cyclotomic polynomial are distinct in every field of characteristic p, as this polynomial is a divisor of Xⁿ − 1, whose discriminant ${\displaystyle n^{n}}$ is nonzero modulo p. It follows that the nth cyclotomic polynomial factors over GF(p) into distinct irreducible polynomials that have all the same degree, say d, and that GF(p^d) is the smallest field of characteristic p that contains the nth primitive roots of unity.

The field GF(64) has several interesting properties that smaller fields do not share: it has two subfields such that neither is contained in the other; not all generators (elements with minimal polynomial of degree 6 over GF(2)) are primitive elements; and the primitive elements are not all conjugate under the Galois group.

The order of this field being 2⁶, and the divisors of 6 being 1, 2, 3, 6, the subfields of GF(64) are GF(2), GF(2²) = GF(4), GF(2³) = GF(8), and GF(64) itself. As 2 and 3 are coprime, the intersection of GF(4) and GF(8) in GF(64) is the prime field GF(2).

The union of GF(4) and GF(8) has thus 10 elements. The remaining 54 elements of GF(64) generate GF(64) in the sense that no other subfield contains any of them. It follows that they are roots of irreducible polynomials of degree 6 over GF(2). This implies that, over GF(2), there are exactly 9 = 54/6 irreducible monic polynomials of degree 6. This may be verified by factoring X⁶⁴ − X over GF(2).

The elements of GF(64) are primitive nth roots of unity for some n dividing 63. As the 3rd and the 7th roots of unity belong to GF(4) and GF(8), respectively, the 54 generators are primitive nth roots of unity for some n in {9, 21, 63}. Euler's totient function shows that there are 6 primitive 9th roots of unity, 12 primitive 21st roots of unity, and 36 primitive 63rd roots of unity. Summing these numbers, one finds again 54 elements.

By factoring the cyclotomic polynomials over GF(2), one finds that:

• The six primitive 9th roots of unity are roots of

${\displaystyle X^{6}+X^{3}+1,}$

and are all conjugate under the action of the Galois group.

• The twelve primitive 21st roots of unity are roots of

${\displaystyle (X^{6}+X^{4}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X^{2}+1).}$

They form two orbits under the action of the Galois group. As the two factors are reciprocal to each other, a root and its (multiplicative) inverse do not belong to the same orbit.

• The 36 primitive elements of GF(64) are the roots of

${\displaystyle (X^{6}+X^{4}+X^{3}+X+1)(X^{6}+X+1)(X^{6}+X^{5}+1)(X^{6}+X^{5}+X^{3}+X^{2}+1)(X^{6}+X^{5}+X^{2}+X+1)(X^{6}+X^{5}+X^{4}+X+1),}$

They split into 6 orbits of 6 elements under the action of the Galois group.

This shows that the best choice to construct GF(64) is to define it as GF(2)[X] / (X⁶ + X + 1). In fact, this generator is a primitive element, and this polynomial is the irreducible polynomial that produces the easiest Euclidean division.

The polynomial

${\displaystyle 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 = pⁿ then X^q − X is the product of all monic irreducible polynomials over GF(p), whose degree divides n. In fact, if P is an irreducible factor over GF(p) of X^q − X, its degree divides n, as its splitting field is contained in GF(pⁿ). Conversely, if P is an irreducible monic polynomial over GF(p) of degree d dividing n, it defines a field extension of degree d, which is contained in GF(pⁿ), and all roots of P belong to GF(pⁿ), and are roots of X^q − X; thus P divides X^q − X. As X^q − X does not have any multiple factor, it is thus the product of all the irreducible monic polynomials that divide it.

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

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

${\displaystyle N(q,n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)q^{n/d},}$

where μ is the Möbius function. This formula is almost a direct consequence of above property of X^q − 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

${\displaystyle N(q,n)\geq {\frac {1}{n}}\left(q^{n}-\sum _{p\mid n,\ p{\text{ prime}}}q^{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.

A finite field F is not algebraically closed: the polynomial

${\displaystyle f(T)=1+\prod _{\alpha \in F}(T-\alpha ),}$

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

Fix an algebraic closure ${\displaystyle {\overline {\mathbb {F} }}_{q}}$ of ${\displaystyle \mathbb {F} _{q}}$. The map ${\displaystyle \varphi _{q}\colon {\overline {\mathbb {F} }}_{q}\to {\overline {\mathbb {F} }}_{q}}$ sending each x to x^q is called the qth power Frobenius automorphism. The subfield of ${\displaystyle {\overline {\mathbb {F} }}_{q}}$ fixed by the nth iterate of ${\displaystyle \varphi _{q}}$ is the set of zeros of the polynomial x^qn − x, which has distinct roots since its derivative in ${\displaystyle \mathbb {F} _{q}[x]}$ is −1, which is never zero. Therefore that subfield has qⁿ elements, so it is the unique copy of ${\displaystyle \mathbb {F} _{q^{n}}}$ in ${\displaystyle {\overline {\mathbb {F} }}_{q}}$. Every finite extension of ${\displaystyle \mathbb {F} _{q}}$ in ${\displaystyle {\overline {\mathbb {F} }}_{q}}$ is this ${\displaystyle \mathbb {F} _{q^{n}}}$ for some n, so

${\displaystyle {\overline {\mathbb {F} }}_{q}=\bigcup _{n\geq 1}\mathbb {F} _{q^{n}}.}$

The absolute Galois group of ${\displaystyle \mathbb {F} _{q}}$ is the profinite group

${\displaystyle \operatorname {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})\simeq \varprojlim _{n}\operatorname {Gal} ({\overline {\mathbb {F} }}_{q^{n}}/\mathbb {F} _{q})\simeq \varprojlim _{n}(\mathbf {Z} /n\mathbf {Z} )={\widehat {\mathbf {Z} }}.}$

Like any infinite Galois group, ${\displaystyle \operatorname {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})}$ may be equipped with the Krull topology, and then the isomorphisms just given are isomorphisms of topological groups. The image of ${\displaystyle \varphi _{q}}$ in the group ${\displaystyle \operatorname {Gal} ({\overline {\mathbb {F} }}_{q^{n}}/\mathbb {F} _{q})\simeq \mathbf {Z} /n\mathbf {Z} }$ is the generator 1, so ${\displaystyle \varphi _{q}}$ corresponds to ${\displaystyle 1\in {\widehat {\mathbf {Z} }}}$. It follows that ${\displaystyle \varphi _{q}}$ has infinite order and generates a dense subgroup of ${\displaystyle \operatorname {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})}$, not the whole group, because the element ${\displaystyle 1\in {\widehat {\mathbf {Z} }}}$ has infinite order and generates the dense subgroup ${\displaystyle \mathbf {Z} \subsetneqq {\widehat {\mathbf {Z} }}.}$ One says that ${\displaystyle \varphi _{q}}$ is a topological generator of ${\displaystyle \operatorname {Gal} ({\overline {\mathbb {F} }}_{q}/\mathbb {F} _{q})}$.

Although finite fields are not algebraically closed, they are quasi-algebraically closed, which means that every homogeneous polynomial over a finite field has a non-trivial zero whose components are in the field if the number of its variables is more than its degree. This was a conjecture of Artin and Dickson proved by Chevalley (see Chevalley–Warning 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.[9]