Finite field

A finite field is a field whose underlying set contains finitely many elements. The smallest examples are the integers modulo a prime p, written GF(p)F_p; arithmetic wraps around after reduction modulo p.¹ Every finite field has characteristic p, meaning that adding its multiplicative identity to itself p times gives zero. Its number of elements is necessarily pⁿ, where n is a positive integer. For each such size there is, up to a field-preserving relabeling called an isomorphism, exactly one finite field. Thus GF(16) is unique in structure even though it can be represented in different ways.

Larger finite fields are constructed by adjoining a root of an irreducible polynomial to a prime field. If f(x) has degree n over GF(p), the quotient ring GF(p)[x]/(f) is a field with pⁿ elements. Elements are represented by polynomials of degree below n, with coefficients reduced modulo p; multiplication is followed by reduction using f. Different irreducible polynomials produce different coordinate descriptions of isomorphic fields. The Frobenius automorphism, which maps a to a^p, is central to computations: its repeated application generates the field's Galois group over GF(p), and its fixed elements form the base field.

The nonzero elements of a finite field form a cyclic multiplicative group of order pⁿ−1, so every nonzero element has a multiplicative inverse and a power dividing that order.¹ Finite fields support polynomial factorization, efficient exponentiation, and finite versions of linear algebra. In coding theory, Reed–Solomon and related error-correcting codes perform symbol arithmetic in fields such as GF(2⁸). The Advanced Encryption Standard represents bytes as elements of GF(2⁸) and uses inversion there in its substitution construction. Public-key systems also use finite fields, including elliptic-curve cryptography over prime fields and binary fields.

Finite fields have a richer subfield structure than their size alone suggests. GF(p^m) is a subfield of GF(pⁿ) exactly when m divides n. The polynomial x^pn−x has every element of GF(pⁿ) as a root, making it a compact way to describe the field and its subfields. A field may be implemented with a polynomial basis, a normal basis, or other coordinates; these representations change speed and storage without changing the abstract field. The same arithmetic also appears in less conspicuous settings, including linear-feedback shift registers, combinatorial designs, finite geometries, and algorithms for factoring polynomials over finite domains.²

Prime field

The field GF(p) consisting of the integers modulo a prime p.

Characteristic

The least positive number of additions of the multiplicative identity that gives zero; for a finite field it is prime.

Irreducible polynomial

A nonconstant polynomial that cannot be factored into lower-degree nonconstant polynomials over the specified field.

Frobenius automorphism

The field automorphism sending each element a to aᵖ in a field of characteristic p.

Galois field

Another name for a finite field, commonly abbreviated GF(q).