Finite Field

A finite field is a field containing finitely many elements: addition, subtraction, multiplication, and division by any nonzero element are defined and satisfy the field axioms. Finite fields are also called Galois fields, and a field with $q$ elements is commonly written $\mathbb F_q$ or $\mathrm{GF}(q)$. Their defining classification states that $q$ must be a prime power, and that for every prime power there is exactly one finite field up to isomorphism. They provide finite settings for algebraic operations without sacrificing the ability to divide. (kconrad.math.uconn.edu)

Characteristic and possible sizes

The characteristic of a finite field is the smallest positive integer $p$ for which

This integer must be a prime number. If it were composite, say $p=ab$ with $1<a,b<p$, then the nonzero elements $a\cdot1$ and $b\cdot1$ would have product zero, which is impossible in a field. The multiples of $1$ form its prime subfield, isomorphic to $\mathbb F_p$. (math.mit.edu)

Every finite field is a vector space over this subfield. If its dimension is $n$, choosing a basis expresses each element uniquely using $n$ coefficients from $\mathbb F_p$. Consequently its cardinality, also called its order, is $p^n$. Thus fields of orders $4$, $8$, $9$, and $25$ exist, but fields of orders $6$ or $10$ do not. The exponent $n$ is the degree of the field extension over $\mathbb F_p$. (math.mit.edu)

Construction and examples

For prime $p$, the simplest construction is

Its elements are residue classes of integers, with operations performed using modular arithmetic. For example, in $\mathbb F_5$, $3+4=2$ and $2\cdot3=1$, so $3$ is the multiplicative inverse of $2$. In contrast, arithmetic modulo a composite integer produces a ring rather than a field: modulo $6$, the nonzero classes $2$ and $3$ multiply to zero. (kconrad.math.uconn.edu)

Larger fields can be constructed with polynomials. Choose an irreducible polynomial $f(x)$ of degree $n$ over $\mathbb F_p$, meaning that it cannot factor into two positive-degree polynomials over that field. The quotient ring

is then a field with $p^n$ elements. Its elements have unique representatives of degree less than $n$. Addition is coefficientwise; multiplication is polynomial multiplication followed by reduction modulo $f(x)$. Irreducibility ensures that every nonzero class has an inverse. (math.mit.edu)

For instance, $x^2+x+1$ is irreducible over $\mathbb F_2$. Writing $\alpha$ for the class of $x$, the resulting field is

Thus $\alpha(\alpha+1)=1$. This field is not arithmetic modulo $4$: in $\mathbb F_4$, $1+1=0$, whereas modulo $4$, $1+1=2$. Different irreducible polynomials of the same degree can give different representations of an isomorphic field. (maths.dur.ac.uk)

Multiplicative structure and polynomial identities

The nonzero elements of $\mathbb F_q$ form a cyclic group under multiplication, of order $q-1$. Hence there is a primitive element $g$ such that every nonzero element is a power of $g$. This multiplicative structure differs from the additive structure, which is that of an $n$-dimensional vector space over $\mathbb F_p$. (kconrad.math.uconn.edu)

Every nonzero $a\in\mathbb F_q$ satisfies $a^{q-1}=1$, and every element satisfies $a^q=a$. Therefore

Conversely, the roots of $x^{p^n}-x$ in its splitting field form a field with exactly $p^n$ elements. This establishes existence; uniqueness of splitting fields establishes uniqueness up to isomorphism. The polynomial has distinct roots because its formal derivative is $-1$. (jmilne.org)

Polynomial expressions and polynomial functions must be distinguished. The nonzero polynomial $x^q-x$ induces the zero function on $\mathbb F_q$. More generally, every function from $\mathbb F_q$ to itself has a unique polynomial representative of degree less than $q$, obtained by interpolation. (kconrad.math.uconn.edu)

Frobenius and subfields

The Frobenius automorphism

preserves addition and multiplication in characteristic $p$. On $\mathbb F_{p^n}$, it has order $n$; every automorphism fixing $\mathbb F_p$ is one of its powers. Accordingly, the extension is Galois with a cyclic automorphism group, an explicit example of Galois theory. (jmilne.org)

The subfields are completely determined by divisibility: $\mathbb F_{p^n}$ contains a subfield with $p^m$ elements exactly when $m$ divides $n$, and that subfield is unique. It consists of the elements satisfying $a^{p^m}=a$. For example, $\mathbb F_{64}$ has proper subfields of orders $2$, $4$, and $8$, but none of order $16$. (jmilne.org)

Computation and applications

Finite-field arithmetic uses exact finite representations. Polynomial-based implementations reduce coefficients modulo $p$ and products modulo a chosen irreducible polynomial. In characteristic $2$, coefficient addition corresponds to exclusive OR on bits. Inverses can be computed using the extended Euclidean algorithm for polynomials. (math.mit.edu)

Finite fields support algebraic error-correcting codes, in which symbols and codewords are organized using polynomial or linear-algebraic relations. These relations introduce redundancy that permits detection and correction of transmission errors. (math.mit.edu)

In cryptography, the Advanced Encryption Standard interprets bytes as elements of $\mathbb F_{2^8}$, using the reduction polynomial

Its substitution transformation uses multiplicative inversion, with zero treated separately, followed by an affine transformation; its column-mixing transformation also uses arithmetic in this field. (nvlpubs.nist.gov)