Finite field (${\mathbb{F}}_q$)

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

In a splitting field of $x^{p^n}-x$ over a prime field, the polynomial roots form a field. Frobenius identities close the polynomial roots under addition and multiplication, and nonzero polynomial roots have inverses which are again polynomial roots. The derivative is minus one, so the polynomial has exactly $p^n$ distinct polynomial roots. This constructs a field of every prime-power order.

A finite field has positive characteristic, because its repeated sums of $1$ cannot all be distinct. By the characteristic of an integral domain theorem, this is a prime number $p$. Its multiples of $1$ form a copy of the prime field ${\mathbb{F}}_p$: a nonzero multiple $a1$ has inverse $b1$, where the Bezout identity $ab+cp=1$ supplies $b$.

View $F$ as a vector space over this prime field. Repeatedly extend a linearly independent set until it is maximal; the procedure terminates because $F$ is finite. Maximality makes it a basis. If the dimension is $d$, unique coordinates give exactly $p^d$ elements. Thus the cardinality is a power of a single prime, rather than an arbitrary composite integer.

For a finite field with $q$ elements, exactly $q+1$ functions from the field to itself preserve multiplication, without requiring additivity or preservation of the identity. They are the constant-zero map, the constant-one map, and the $q-1$ power maps $x\mapsto x^k$ for $1\le k\le q-1$.

To prove completeness, $f(1{)}^2=f(1)$ forces $f(1)\in \{0,1\}$ because a field has no zero divisors. The zero choice forces the constant-zero map. For $f(1)=1$, nonzero elements must map to nonzero elements, and the restriction is a group homomorphism of the cyclic multiplicative group of a finite field. Its generator has $q-1$ possible images, giving the $q-1$ power maps on nonzero elements. Setting $f(0)=0$ extends each. The only further possibility is $f(0)=1$, which forces every value to be one. For $q=5$, this gives six maps. These are generally not field homomorphisms, because preservation of addition was never required.

The cosets of the index-$m$ subgroup of the multiplicative group of a finite field are its cyclotomic classes of index $m$. For a character with $\chi (\gamma )={\zeta }_m$, their indicators are $1_{C_j}(x)=m^{-1}{\sum }_{h=0}^{m-1}{\zeta }_m^{-jh}{\chi }^h(x)$, with every character extended by zero at zero. Jacobi sums of finite-field characters imply $|C_i\cap (t+C_j)|=q/m^2+O_m(\sqrt{q})$ uniformly for $t\ne 0$.

Fix finitely many prescribed cyclotomic classes for pairwise differences. Such patterns are realized in every sufficiently large compatible finite field. For $r$ already chosen coordinates, let $M(a)$ count extensions with prescribed classes for $x-a_i$. Averaging over all $a\in {\mathbb{F}}_q^r$ gives $\mathbb{E}M=q/m^r+O(1)$ and, from the uniform two-class intersection estimate, $\mathrm{Var}M=O_{m,r}(q^{3/2})$. The Chebyshev inequality makes the fraction with $M<q/(2m^r)$ tend to zero. Inductively each fixed pattern on $r$ coordinates occupies a positive proportion of all tuples, so some positive proportion have many extensions. This proves the pattern-existence claim without an unproved greedy-extension assumption.

The finite field ${\mathbb{F}}_9$ can be represented as ${\mathbb{F}}_3[X]/(X^2+1)$, since the quadratic has no root modulo three. Its elements are $a+b\beta$ for $a,b\in {\mathbb{F}}_3$, with ${\beta }^2=-1$. Multiplication reduces to $(a+b\beta )(c+d\beta )=(ac-bd)+(ad+bc)\beta$ modulo three.

Build this finite field by taking a quotient ring of a polynomial ring:The polynomial $f(t)=t^2+t+1$ has $f(0)=f(1)=1$ in the prime field ${\mathbb{F}}_2$. A polynomial of polynomial degree two is an irreducible polynomial exactly when it has no polynomial root in the coefficient field. Thus the quotient by an irreducible polynomial is a field construction applies. Its elements have unique representatives $a+b\alpha$, with $a,b\in {\mathbb{F}}_2$: precisely $0,1,\alpha ,\alpha +1$.

The defining relation is ${\alpha }^2+\alpha +1=0$. Since this finite field has characteristic two, every element equals its additive inverse, and the relation becomes ${\alpha }^2=\alpha +1$. Addition acts separately on the two coefficients:All coefficient calculations use modular arithmetic modulo two. For example, $(\alpha +1)+\alpha =1$ and $(\alpha +1)+(\alpha +1)=0$. Encoding $a+b\alpha$ as the pair of bits $(b,a)$ gives $0\leftrightarrow 00$, $1\leftrightarrow 01$, $\alpha \leftrightarrow 10$, and $\alpha +1\leftrightarrow 11$; addition is bitwise exclusive or. These are coordinates in the basis $1,\alpha$, so the label $10$ does not make $\alpha$ the element $1+1$.

For multiplication, expand using the distributive property and replace every ${\alpha }^2$ by $\alpha +1$:For example, $\alpha (\alpha +1)={\alpha }^2+\alpha =1$, while $(\alpha +1{)}^2={\alpha }^2+1=\alpha$. The following complete tables are computed from the coefficient rules. Colors identify results, rather than their numerical sizes. Every row of the addition table lists all four elements, and every nonzero row of the multiplication table does too: adding an element, or multiplying by a nonzero element, can be undone.

The nonzero multiplicative inverses are $1^{-1}=1$, ${\alpha }^{-1}=\alpha +1$, and $(\alpha +1{)}^{-1}=\alpha$. Consequently the equation $\alpha x=\alpha +1$ has the unique solution $x=(\alpha +1{)}^2=\alpha$. Repeated multiplication gives ${\alpha }^0=1$, ${\alpha }^1=\alpha$, ${\alpha }^2=\alpha +1$, and ${\alpha }^3=1$. They cycle through every element of the multiplicative group of a finite field.

Compare the ring $\mathbb{Z}/4\mathbb{Z}$, also with four elements. Its addition satisfies $1+1=2\ne 0$, and its multiplication satisfies $2^2=0$. Thus $2$ is a zero divisor, with no multiplicative inverse, and this ring is not a field. Multiplying by $2$ collapses different inputs to the same output: both $0$ and $2$ give $0$, while both $1$ and $3$ give $2$. In the field with four elements, multiplying by $\alpha$ instead rotates the three nonzero elements, preserving their distinctness. The figure makes visible why counting four elements alone does not specify their arithmetic.

In a splitting field over ${\mathbb{F}}_q$, the polynomial $X^{q^n}-X$ has $q^n$ distinct roots because its derivative is $-1$. Its roots are closed under addition, multiplication, additive inverses, and nonzero inverses, so they form the field ${\mathbb{F}}_{q^n}$. The splitting field consequently has degree $n$ over ${\mathbb{F}}_q$.

Every monic irreducible polynomial over ${\mathbb{F}}_q$ whose degree divides $n$ divides $X^{q^n}-X$. In particular, if $f$ has degree $n$ and $\alpha$ is one of its roots, then ${\mathbb{F}}_q(\alpha )$ has $q^n$ elements, so ${\alpha }^{q^n}=\alpha$ and the minimal polynomial $f$ divides $X^{q^n}-X$.

Let $N_q(n)$ be the number of monic irreducible polynomials of polynomial degree $n$ over ${\mathbb{F}}_q$. Factoring $X^{q^n}-X$ into all such polynomials whose degrees divide $n$ givesThe Möbius inversion formula therefore gives

Every degree-$n$ extension of ${\mathbb{F}}_q$ is isomorphic to ${\mathbb{F}}_{q^n}$.

For ${\mathbb{F}}_{q^2}/{\mathbb{F}}_q$, the field norm maps the nonzero elements onto ${\mathbb{F}}_q^{\ast }$: the multiplicative group of a finite field is cyclic, and the power $q+1$ has image of order $q-1$. The field trace is also onto. Indeed it is an ${\mathbb{F}}_q$-linear map into ${\mathbb{F}}_q$, and is not zero because its polynomial $X+X^q$ has degree $q$ and cannot vanish at all $q^2$ field elements. Consequently $a\mapsto \mathrm{Tr}(ac)$ is onto whenever $c\ne 0$.

The map $x\mapsto x^q$ is an automorphism of ${\mathbb{F}}_{q^n}$ fixing ${\mathbb{F}}_q$. Its powers are all the ${\mathbb{F}}_q$-automorphisms, and its order is $n$.

Over ${\mathbb{F}}_q$, the roots of the minimal polynomial of $\alpha \in {\mathbb{F}}_{q^n}$ are its distinct iterates $\alpha ,{\alpha }^q,{\alpha }^{q^2},\dots$ under the finite-field Frobenius automorphism.

Every finite field extension is a Galois extension, and

The multiplicative group of a finite field ${\mathbb{F}}_q$ is the group ${\mathbb{F}}_q^{\times }$ of its $q-1$ nonzero elements under multiplication. Zero is excluded because it has no multiplicative inverse. In the field with four elements, these elements are $1,\alpha ,\alpha +1$, obtained by repeated multiplication by $\alpha$: they form a cyclic group of group order three. Its addition behaves differently: every nonzero element added to itself gives zero. Keeping the two operations distinct prevents confusing the size of the finite field with the group order of its multiplicative group of a finite field.

A primitive element of ${\mathbb{F}}_q$ generates its multiplicative group. This implies ${\mathbb{F}}_q={\mathbb{F}}_p(\alpha )$, but an element generating the field extension need not generate the multiplicative group. For instance $u\in {\mathbb{F}}_3[u]/(u^2+1)$ generates the quadratic extension but has order four, whereas $1+u$ has order eight and is multiplicatively primitive.

A monic polynomial of degree $m$ over ${\mathbb{F}}_q$ that is an irreducible polynomial is primitive in the finite-field sense when one of its roots generates the multiplicative group of a finite field ${\mathbb{F}}_{q^m}^{\times }$. All its roots are Frobenius conjugates and then have the same order $q^m-1$. This notion differs from a primitive polynomial over an integral domain, which concerns the common divisor of its coefficients. Primitive finite-field polynomials provide explicit field representations and primitive cyclic Reed-Solomon codes or BCH codes.

A nonzero element $a$ of a finite field is a quartic residue when $a=b^4$ for some nonzero $b$. If $q\equiv 1(\mathrm{mod}4)$, the multiplicative group of a finite field is cyclic of order divisible by four, so the quartic residues form a subgroup of index four; equivalently $a^{(q-1)/4}=1$.

The nonzero elements of every finite field form a cyclic group. For a field with $q$ elements, combine elements realizing each prime-power factor of the group exponent to obtain an element of exponent order; the root bound for $X^m-1$ then forces that order to be $q-1$.

Every finite subgroup $H$ of the multiplicative group of a field is cyclic. If $m$ is the exponent of $H$, commutativity lets one combine elements whose orders realize the prime-power factors of $m$, producing an element of order $m$. Every element of $H$ is a root of $X^m-1$, so the Lagrange root bound over a field gives $|H|\le m$. Since $m\le |H|$, equality holds and that element generates $H$.

In a finite field with $q$ elements, the equation $x^k=1$ has exactly $\gcd (k,q-1)$ solutions. Indeed, after choosing a generator $g$ of the multiplicative group, $x=g^j$ is a solution exactly when $(q-1)\mid kj$.

For odd $p$, the nonzero squares form an index-two subgroup of ${\mathbb{F}}_p^{\times }$. Given nonzero $a,b$, either $a$ or $b$ is a square, or both occupy the nontrivial coset and $ab$ is a square. Taking $a=2$ and $b=3$ shows that one of $2,3,6$ is a square, apart from the immediate zero case $p=3$.