finite field

A finite field is a finite set that is a field; this means that multiplication, addition, subtraction and division (excluding division by zero) are defined and satisfy the rules of arithmetic known as the field axioms.{{Cite book |last=Dummit |first=David Steven |title=Abstract algebra |last2=Foote |first2=Richard M. |date=2004 |publisher=Wiley |isbn=978-0-471-43334-7 |edition=3rd |location=Hoboken, NJ}}

The number of elements of a finite field is called its order or, sometimes, its size. A finite field of order $q$ exists if and only if $q$ is a prime power $p^k$ (where $p$ is a prime number and $k$ is a positive integer). In a field of order $p^k$, adding $p$ copies of any element always results in zero; that is, the characteristic of the field is $p$.

For $q=p^k$, all fields of order $q$ are isomorphic (see {{slink||Existence and uniqueness}} below). Moreover, a field cannot contain two different finite subfields with the same order. One may therefore identify all finite fields with the same order, and they are unambiguously denoted $\backslash mathbb\{F\}\_\{q\}$, $\backslash mathbf\{F\}\_q$ or $\backslash mathrm\{GF\}(q)$, where the letters GF stand for "Galois field".This latter notation was introduced by E. H. Moore in an address given in 1893 at the International Mathematical Congress held in Chicago {{harvnb|Mullen|Panario|2013|loc = p. 10}}.

In a finite field of order $q$, the polynomial $X^q-X$ has all $q$ elements of the finite field as roots.{{Citation needed|date=April 2025}} The non-zero elements of a finite field form a multiplicative group. This group is cyclic, so all non-zero elements can be expressed as powers of a single element called a primitive element of the field. (In general there will be several primitive elements for a given field.)

The simplest examples of finite fields are the fields of prime order: for each prime number $p$, the prime field of order $p$ may be constructed as the integers modulo $p$, $\backslash mathbb\{Z\}/p\backslash mathbb\{Z\}$.

The elements of the prime field of order $p$ may be represented by integers in the range $0,\backslash ldots,p\; -\; 1$. The sum, the difference and the product are the remainder of the division by $p$ of the result of the corresponding integer operation. The multiplicative inverse of an element may be computed by using the extended Euclidean algorithm (see {{slink|Extended Euclidean algorithm|Modular integers}}).{{Citation needed|date=April 2025}}

Let $F$ be a finite field. For any element $x$ in $F$ and any integer $n$, denote by $n\; \backslash cdot\; x$ the sum of $n$ copies of $x$. The least positive $n$ such that $n\; \backslash cdot\; 1\; =\; 0$ is the characteristic $p$ of the field. This allows defining a multiplication $(k,x)\; \backslash mapsto\; k\; \backslash cdot\; x$ of an element $k$ of $\backslash mathrm\{GF\}(p)$ by an element $x$ of $F$ by choosing an integer representative for $k$. This multiplication makes $F$ into a $\backslash mathrm\{GF\}(p)$-vector space. It follows that the number of elements of $F$ is $p^n$ for some integer $n$.

The identity

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

(sometimes called the freshman's dream) is true in a field of characteristic $p$. This follows from the binomial theorem, as each binomial coefficient of the expansion of $(x+y)^p$, except the first and the last, is a multiple of $p$.{{Citation needed|date=April 2025}}

By Fermat's little theorem, if $p$ is a prime number and $x$ is in the field $\backslash mathrm\{GF\}(p)$ then $x^p=x$. This implies the equality

$$X^p-X=\backslash prod\_\{a\backslash in\; \backslash mathrm\{GF\}(p)\}\; (X-a)$$

for polynomials over $\backslash mathrm\{GF\}(p)$. More generally, every element in $\backslash mathrm\{GF\}(p^n)$ satisfies the polynomial equation $x^\{p^n\}-x=0$.{{Citation needed|date=April 2025}}

Any finite field extension of a finite field is separable and simple. That is, if $E$ is a finite field and $F$ is a subfield of $E$, then $E$ is obtained from $F$ by adjoining a single element whose minimal polynomial is separable. To use a piece of jargon, finite fields are perfect.

A more general algebraic structure that satisfies all the other axioms of a field, but whose multiplication is not required to be commutative, is called a division ring (or sometimes skew field). By Wedderburn's little theorem, any finite division ring is commutative, and hence is a finite field.

Let $q=p^n$ be a prime power, and $F$ be the splitting field of the polynomial

$$P\; =\; X^q-X$$

over the prime field $\backslash mathrm\{GF\}(p)$. This means that $F$ is a finite field of lowest order, in which $P$ has $q$ distinct roots (the formal derivative of $P$ is $P\text{'}=-1$, implying that $\backslash mathrm\{gcd\}(P,P\text{'})=1$, which in general implies that the splitting field is a separable extension of the original). The 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 words, 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. Also, if a field $F$ has a field of order $q=p^k$ as a subfield, its elements are the $q$ roots of $X^q-X$, and $F$ cannot contain another subfield of order $q$.

In summary, we have the following classification theorem first proved in 1893 by E. H. Moore:{{citation|first=E. H.|last=Moore|author-link=E. H. Moore|chapter=A doubly-infinite system of simple groups|editor=E. H. Moore |display-editors=etal |title=Mathematical Papers Read at the International Mathematics Congress Held in Connection with the World's Columbian Exposition|pages=208–242|publisher=Macmillan & Co.|year=1896}}

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 $\backslash mathrm\{GF\}(p^n)$ contains a subfield isomorphic to $\backslash mathrm\{GF\}(p^m)$ if and only if $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$.

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

$$\backslash mathrm\{GF\}(q)\; =\; \backslash mathrm\{GF\}(p)[X]/(P)$$

of the polynomial ring $\backslash mathrm\{GF\}(p)[X]$ by the ideal generated by $P$ is a field of order $q$.

More explicitly, the elements of $\backslash mathrm\{GF\}(q)$ are the polynomials over $\backslash mathrm\{GF\}(p)$ whose degree is strictly less than $n$. The addition and the subtraction are those of polynomials over $\backslash mathrm\{GF\}(p)$. The product of two elements is the remainder of the Euclidean division by $P$ of the product in $\backslash mathrm\{GF\}(q)[X]$.

The multiplicative inverse of a non-zero element may be computed with the extended Euclidean algorithm; see {{slink|Extended Euclidean algorithm#Simple algebraic field extensions}}.

However, with this representation, elements of $\backslash mathrm\{GF\}(q)$ may be difficult to distinguish from the corresponding polynomials. Therefore, it is common to give a name, commonly $\backslash alpha$ to the element of $\backslash mathrm\{GF\}(q)$ that corresponds to the polynomial $X$. So, the elements of $\backslash mathrm\{GF\}(q)$ become polynomials in $\backslash alpha$, where $P(\backslash alpha)=0$, and, when one encounters a polynomial in $\backslash alpha$ of degree greater or equal to $n$ (for example after a multiplication), one knows that one has to use the relation $P(\backslash alpha)=0$ to reduce its degree (it is what Euclidean division is doing).

Except in the construction of $\backslash mathrm\{GF\}(4)$, there are several possible choices for $P$, which produce isomorphic results. To simplify the Euclidean division, one commonly chooses for $P$ a polynomial of the form

$$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^n+aX+b$ may not exist. In characteristic $2$, if the polynomial $X^n+X+1$ is reducible, it is recommended to choose $X^n+X^k+1$ with the lowest possible $k$ that makes the polynomial irreducible. If all these trinomials are reducible, one chooses "pentanomials" $X^n+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.{{citation|publisher=National Institute of Standards and Technology|url=http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf |archive-url=https://web.archive.org/web/20080719074906/http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf |archive-date=2008-07-19 |url-status=live|title=Recommended Elliptic Curves for Government Use|pages=3|date=July 1999}}

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.

The smallest non-prime field is the field with four elements, which is commonly denoted $\backslash mathrm\{GF\}(4)$ or $\backslash mathbb\{F\}\_4.$ It consists of the four elements $0,\; 1,\; \backslash alpha,\; 1\; +\; \backslash alpha$ such that $\backslash alpha^2=1+\backslash alpha$, $1\; \backslash cdot\; \backslash alpha\; =\; \backslash alpha\; \backslash cdot\; 1\; =\; \backslash alpha$, $x+x=0$, and $x\; \backslash cdot\; 0\; =\; 0\; \backslash cdot\; x\; =\; 0$, for every $x\; \backslash in\; \backslash mathrm\{GF\}(4)$, the other operation results being easily deduced from the distributive law. See below for the complete operation tables.

This may be deduced as follows from the results of the preceding section.

Over $\backslash mathrm\{GF\}(2)$, there is only one irreducible polynomial of degree $2$:

$$X^2+X+1$$

Therefore, for $\backslash mathrm\{GF\}(4)$ the construction of the preceding section must involve this polynomial, and

$$\backslash mathrm\{GF\}(4)\; =\; \backslash mathrm\{GF\}(2)[X]/(X^2+X+1).$$

Let $\backslash alpha$ denote a root of this polynomial in $\backslash mathrm\{GF\}(4)$. This implies that

$$\backslash alpha^2\; =\; 1\; +\; \backslash alpha,$$

and that $\backslash alpha$ and $1+\backslash alpha$ are the elements of $\backslash mathrm\{GF\}(4)$ that are not in $\backslash mathrm\{GF\}(2)$. The tables of the operations in $\backslash mathrm\{GF\}(4)$ result from this, and are as follows:

|

|

|}

A table for subtraction is not given, 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$, the values of $x$ must be read in the left column, and the values of $y$ in the top row. (Because $0\; \backslash cdot\; z\; =\; 0$ for every $z$ in every ring the division by 0 has to remain undefined.) From the tables, it can be seen that the additive structure of $\backslash mathrm\{GF\}(4)$ is isomorphic to the Klein four-group, while the non-zero multiplicative structure is isomorphic to the group $Z\_3$.

The map

$$\backslash varphi:x\; \backslash mapsto\; x^2$$

is the non-trivial field automorphism, called the Frobenius automorphism, which sends $\backslash alpha$ into the second root $1+\backslash alpha$ of the above-mentioned irreducible polynomial $X^2+X+1$.

For applying the above general construction of finite fields in the case of $\backslash mathrm\{GF\}(p^2)$, 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^2-r$, with $r$ in $\backslash mathrm\{GF\}(p)$.

More precisely, the polynomial $X^2-r$ is irreducible over $\backslash mathrm\{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 $\backslash frac\{p-1\}\{2\}$ quadratic non-residues modulo $p$. For example, $2$ is a quadratic non-residue for $p=3,5,11,13,\backslash ldots$, and $3$ is a quadratic non-residue for $p=5,7,17,\backslash ldots$. If $p\; \backslash equiv\; 3\; \backslash mod\; 4$, that is $p=3,7,11,19,\backslash ldots$, one may choose $-1\; \backslash equiv\; p\; -\; 1$ as a quadratic non-residue, which allows us to have a very simple irreducible polynomial $X^2+1$.

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

$$a+b\backslash alpha,$$

with $a$ and $b$ in $\backslash mathrm\{GF\}(p)$. The operations on $\backslash mathrm\{GF\}(p^2)$ are defined as follows (the operations between elements of $\backslash mathrm\{GF\}(p)$ represented by Latin letters are the operations in $\backslash mathrm\{GF\}(p)$):

$$\backslash 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)&=(ac + rbd)+ (ad+bc)\alpha\\

(a+b\alpha)^{-1}&=a(a^2-rb^2)^{-1}+(-b)(a^2-rb^2)^{-1}\alpha

\end{align}

The polynomial

$$X^3-X-1$$

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

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

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

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

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

\begin{align}

-(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{align}

The polynomial

$$X^4+X+1$$

is irreducible over $\backslash mathrm\{GF\}(2)$, that is, it is irreducible modulo $2$. It follows that the elements of $\backslash mathrm\{GF\}(16)$ may be represented by expressions

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

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

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

(that is, $\backslash alpha$ is defined as a root of the given irreducible polynomial). As the characteristic of $\backslash mathrm\{GF\}(2)$ is $2$, each element is its additive inverse in $\backslash mathrm\{GF\}(16)$. The addition and multiplication on $\backslash mathrm\{GF\}(16)$ may be defined as follows; in following formulas, the operations between elements of $\backslash mathrm\{GF\}(2)$, represented by Latin letters are the operations in $\backslash mathrm\{GF\}(2)$.

\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\;+\\

&\quad\;(ag+bf+ce +ch+dg+dh)\alpha^2

+(ah+bg+cf+de +dh)\alpha^3

\end{align}

The field $\backslash mathrm\{GF\}(16)$ has eight primitive elements (the elements that have all nonzero elements of $\backslash mathrm\{GF\}(16)$ as integer powers). These elements are the four roots of $X^4+X+1$ and their multiplicative inverses. In particular, $\backslash alpha$ is a primitive element, and the primitive elements are $\backslash alpha^m$ with $m$ less than and coprime with $15$ (that is, 1, 2, 4, 7, 8, 11, 13, 14).

The set of non-zero elements in $\backslash mathrm\{GF\}(q)$ is an abelian group under the multiplication, of order $q-1$. By Lagrange's theorem, there exists a divisor $k$ of $q-1$ such that $x^k=1$ for every non-zero $x$ in $\backslash mathrm\{GF\}(q)$. As the equation $x^k=1$ has at most $k$ solutions in any field, $q-1$ is the lowest possible value for $k$.

The structure theorem of finite abelian groups implies that this multiplicative group is cyclic, that is, all non-zero elements are powers of a single element. In summary:

{{block indent | em = 1.5 | text = The multiplicative group of the non-zero elements in $\backslash mathrm\{GF\}(q)$ is cyclic, i.e., there exists an element $a$, such that the $q-1$ non-zero elements of $\backslash mathrm\{GF\}(q)$ are $a,a^2,\backslash ldots,a^\{q-2\},a^\{q-1\}=1$.}}

Such an element $a$ is called a primitive element of $\backslash mathrm\{GF\}(q)$. Unless $q=2,3$, the primitive element is not unique. The number of primitive elements is $\backslash phi(q-1)$ where $\backslash phi$ is Euler's totient function.

The result above implies that $x^q=x$ for every $x$ in $\backslash mathrm\{GF\}(q)$. The particular case where $q$ is prime is Fermat's little theorem.

If $a$ is a primitive element in $\backslash mathrm\{GF\}(q)$, then for any non-zero element $x$ in $F$, there is a unique integer $n$ with $0\; \backslash le\; n\; \backslash le\; q-2$ such that $x=a^n$.

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

While $a^n$ 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 $\backslash mathrm\{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^n$. The identity

$$a^m+a^n=a^n\backslash left(a^\{m-n\}+1\backslash right)$$

allows one to solve this problem by constructing the table of the discrete logarithms of $a^n+1$, called Zech's logarithms, for $n=0,\backslash ldots,q-2$ (it is convenient to define the discrete logarithm of zero as being $-\backslash infty$).

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 $\backslash mathrm\{GF\}(q)$.

If $n$ is a positive integer, an $n$th primitive root of unity is a solution of the equation $x^n=1$ that is not a solution of the equation $x^m=1$ for any positive integer

The field $\backslash mathrm\{GF\}(q)$ contains a $n$th 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 $n$th roots of unity in $\backslash mathrm\{GF\}(q)$ is $\backslash phi(n)$ (Euler's totient function). The number of $n$th roots of unity in $\backslash mathrm\{GF\}(q)$ is $\backslash mathrm\{gcd\}(n,q-1)$.

In a field of characteristic $p$, every $np$th root of unity is also a $n$th 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 $n$th cyclotomic polynomial are distinct in every field of characteristic $p$, as this polynomial is a divisor of $X^n-1$, whose discriminant $n^n$ is nonzero modulo $p$. It follows that the $n$th cyclotomic polynomial factors over $\backslash mathrm\{GF\}(q)$ into distinct irreducible polynomials that have all the same degree, say $d$, and that $\backslash mathrm\{GF\}(p^d)$ is the smallest field of characteristic $p$ that contains the $n$th primitive roots of unity.

When computing Brauer characters, one uses the map $\backslash alpha^k\; \backslash mapsto\; \backslash exp(2\backslash pi\; i\; k\; /\; (q-1))$ to map eigenvalues of a representation matrix to the complex numbers. Under this mapping, the base subfield $\backslash mathrm\{GF\}(p)$ consists of evenly spaced points around the unit circle (omitting zero).

File:Finite field with 25 elements and base subfield of five elements.jpg

The field $\backslash mathrm\{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 $\backslash mathrm\{GF\}(2)$) are primitive elements; and the primitive elements are not all conjugate under the Galois group.

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

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

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

By factoring the cyclotomic polynomials over $\backslash mathrm\{GF\}(2)$, one finds that:

• The six primitive $9$th roots of unity are roots of $$X^6+X^3+1,$$ and are all conjugate under the action of the Galois group.
• The twelve primitive $21$st roots of unity are roots of $$(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 $\backslash mathrm\{GF\}(64)$ are the roots of $$(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 six orbits of six elements each under the action of the Galois group.

This shows that the best choice to construct $\backslash mathrm\{GF\}(64)$ is to define it as {{math|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.

In this section, $p$ is a prime number, and $q=p^n$ is a power of $p$.

In $\backslash mathrm\{GF\}(q)$, the identity {{math|1=(x + y)^p = x^p + y^p}} implies that the map

$$\backslash varphi:x\; \backslash mapsto\; x^p$$

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

Denoting by {{math|φ^k}} the composition of {{math|φ}} with itself {{math|k}} times, we have

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

It has been shown in the preceding section that {{math|φⁿ}} is the identity. For {{math|0 < k < n}}, the automorphism {{math|φ^k}} is not the identity, as, otherwise, the polynomial

$$X^\{p^k\}-X$$

would have more than {{math|p^k}} roots.

There are no other {{math|GF(p)}}-automorphisms of {{math|GF(q)}}. In other words, {{math|GF(pⁿ)}} has exactly {{math|n}} {{math|GF(p)}}-automorphisms, which are

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

In terms of Galois theory, this means that {{math|GF(pⁿ)}} is a Galois extension of {{math|GF(p)}}, which has a cyclic Galois group.

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

{{main|Factorization of polynomials over finite fields}}

If {{math|F}} is a finite field, a non-constant monic polynomial with coefficients in {{math|F}} is irreducible over {{math|F}}, if it is not the product of two non-constant monic polynomials, with coefficients in {{math|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 fields. 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.

The polynomial

$$X^q-X$$

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

This implies that, if {{math|1=q = pⁿ}} then {{math|X^q − X}} is the product of all monic irreducible polynomials over {{math|GF(p)}}, whose degree divides {{math|n}}. In fact, if {{math|P}} is an irreducible factor over {{math|GF(p)}} of {{math|X^q − X}}, its degree divides {{math|n}}, as its splitting field is contained in {{math|GF(pⁿ)}}. Conversely, if {{math|P}} is an irreducible monic polynomial over {{math|GF(p)}} of degree {{math|d}} dividing {{math|n}}, it defines a field extension of degree {{math|d}}, which is contained in {{math|GF(pⁿ)}}, and all roots of {{math|P}} belong to {{math|GF(pⁿ)}}, and are roots of {{math|X^q − X}}; thus {{math|P}} divides {{math|X^q − X}}. As {{math|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 {{math|GF(p)}}; see Distinct degree factorization.

The number {{math|N(q, n)}} of monic irreducible polynomials of degree {{math|n}} over

{{math|GF(q)}} is given by{{harvnb|Jacobson|2009|loc=§4.13}}

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

where {{math|μ}} is the Möbius function. This formula is an immediate consequence of the property of {{math|X^q − X}} above and the Möbius inversion formula.

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

The exact formula implies the inequality

$$N(q,n)\backslash geq\backslash frac\{1\}\{n\}\; \backslash left(q^n-\backslash sum\_\{\backslash ell\backslash mid\; n,\; \backslash \; \backslash ell\; \backslash text\{\; prime\}\}\; q^\{n/\backslash ell\}\backslash right);$$

this is sharp if and only if {{math|n}} is a power of some prime.

For every {{math|q}} and every {{math|n}}, the right hand side is positive, so there is at least one irreducible polynomial of degree {{math|n}} over {{math|GF(q)}}.

In cryptography, the difficulty of the discrete logarithm problem in finite fields or in elliptic curves is the basis of several widely used protocols, such as the Diffie–Hellman protocol. For example, in 2014, a secure internet connection to Wikipedia involved the elliptic curve Diffie–Hellman protocol (ECDHE) over a large finite field.This can be verified by looking at the information on the page provided by the browser. In coding theory, many codes are constructed as subspaces of vector spaces over finite fields.

Finite fields are used by many error correction codes, such as Reed–Solomon error correction code or BCH code. The finite field almost always has characteristic of {{math|2}}, since computer data is stored in binary. For example, a byte of data can be interpreted as an element of {{math|GF(2⁸)}}. One exception is PDF417 bar code, which is {{math|GF(929)}}. Some CPUs have special instructions that can be useful for finite fields of characteristic {{math|2}}, generally variations of carry-less product.

Finite fields are widely used in number theory, as many problems over the integers may be solved by reducing them modulo one or several prime numbers. For example, the fastest known algorithms for polynomial factorization and linear algebra over the field of rational numbers proceed by reduction modulo one or several primes, and then reconstruction of the solution by using Chinese remainder theorem, Hensel lifting or the LLL algorithm.

Similarly many theoretical problems in number theory can be solved by considering their reductions modulo some or all prime numbers. See, for example, Hasse principle. Many recent developments of algebraic geometry were motivated by the need to enlarge the power of these modular methods. Wiles' proof of Fermat's Last Theorem is an example of a deep result involving many mathematical tools, including finite fields.

The Weil conjectures concern the number of points on algebraic varieties over finite fields and the theory has many applications including exponential and character sum estimates.

Finite fields have widespread application in combinatorics, two well known examples being the definition of Paley Graphs and the related construction for Hadamard Matrices. In arithmetic combinatorics finite fields{{Citation|last=Shparlinski|first=Igor E.|chapter=Additive Combinatorics over Finite Fields: New Results and Applications|publisher=DE GRUYTER|isbn=9783110283600|doi=10.1515/9783110283600.233|title=Finite Fields and Their Applications| year=2013|pages=233–272}} and finite field models{{Citation|last=Green|first=Ben|chapter=Finite field models in additive combinatorics|pages=1–28|publisher=Cambridge University Press|isbn=9780511734885| doi=10.1017/cbo9780511734885.002| title=Surveys in Combinatorics 2005|year=2005|arxiv=math/0409420|s2cid=28297089}}{{Cite journal|last=Wolf|first=J.| date=March 2015|title=Finite field models in arithmetic combinatorics – ten years on|journal=Finite Fields and Their Applications | volume=32|pages=233–274|doi=10.1016/j.ffa.2014.11.003|issn=1071-5797|doi-access=free|hdl=1983/d340f853-0584-49c8-a463-ea16ee51ce0f|hdl-access=free}} are used extensively, such as in Szemerédi's theorem on arithmetic progressions.

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, and hence are finite fields. This result holds even if we relax the associativity axiom to alternativity, that is, all finite alternative division rings are finite fields, by the Artin–Zorn theorem.{{cite book | last=Shult | first=Ernest E. | title=Points and lines. Characterizing the classical geometries | series=Universitext | location=Berlin | publisher=Springer-Verlag | year=2011 | isbn=978-3-642-15626-7 | zbl=1213.51001 | page=123 }}

A finite field $F$ is not algebraically closed: the polynomial

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

has no roots in $F$, since {{math|1=f (α) = 1}} for all $\backslash alpha$ in $F$.

Given a prime number {{mvar|p}}, let $\backslash overline\{\backslash mathbb\{F\}\}\_p$ be an algebraic closure of $\backslash mathbb\{F\}\_p.$ It is not only unique up to an isomorphism, as do all algebraic closures, but contrarily to the general case, all its subfield are fixed by all its automorphisms, and it is also the algebraic closure of all finite fields of the same characteristic {{mvar|p}}.

This property results mainly from the fact that the elements of $\backslash mathbb\; F\_\{p^n\}$ are exactly the roots of $x^\{p^n\}-x,$ and this defines an inclusion $\backslash mathbb\; \backslash mathbb\; F\_\{p^n\}\backslash subset\; \backslash mathbb\; F\_\{p^\{nm\}\}$ for $m>1.$ These inclusions allow writing informally $$\backslash overline\{\backslash mathbb\{F\}\}\_p\; =\; \backslash bigcup\_\{n\; \backslash ge\; 1\}\; \backslash mathbb\{F\}\_\{p^n\}.$$ The formal validation of this notation results from the fact that the above field inclusions form a directed set of fields; Its direct limit is $\backslash overline\{\backslash mathbb\{F\}\}\_p,$ which may thus be considered as "directed union".

Given a primitive element $g\_\{mn\}$ of $\backslash mathbb\{F\}\_\{q^\{mn\}\},$ then $g\_\{mn\}^m$ is a primitive element of $\backslash mathbb\{F\}\_\{q^\{n\}\}.$

For explicit computations, it may be useful to have a coherent choice of the primitive elements for all finite fields; that is, to choose the primitive element $g\_\{n\}$ of $\backslash mathbb\{F\}\_\{q^\{n\}\}$ in order that, whenever $n=mh,$ one has $g\_\{m\}=g\_n^h,$ where $g\_\{m\}$ is the primitive element already chosen for $\backslash mathbb\{F\}\_\{q^\{m\}\}.$

Such a construction may be obtained by Conway polynomials.

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).

• Elementary abelian group
• Field with one element
• Finite field arithmetic
• Finite ring
• Finite group
• Galois ring
• Hamming space
• Quasi-finite field

{{Reflist|colwidth=30em}}

{{refbegin}}

• W. H. Bussey (1905) "Galois field tables for {{nowrap|pⁿ ≤ 169}}", Bulletin of the American Mathematical Society 12(1): 22–38, {{doi|10.1090/S0002-9904-1905-01284-2}}
• W. H. Bussey (1910) "Tables of Galois fields of order < 1000", Bulletin of the American Mathematical Society 16(4): 188–206, {{doi|10.1090/S0002-9904-1910-01888-7}}
• {{citation

| last=Jacobson

| first=Nathan

| author-link=Nathan Jacobson

| title=Basic algebra I

| year=2009

| edition=Second

| publisher=Dover Publications

| isbn=978-0-486-47189-1

| orig-year=1985

}}

• {{citation

| last1=Mullen

| first1=Gary L.

| last2=Mummert

| first2=Carl

| title=Finite Fields and Applications I

| year=2007

| publisher=Student Mathematical Library (AMS)

| isbn=978-0-8218-4418-2

}}

• {{citation|first1=Gary L.|last1=Mullen|first2=Daniel|last2=Panario|title=Handbook of Finite Fields|year=2013|publisher=CRC Press|isbn=978-1-4398-7378-6}}
• {{Citation | last1=Lidl | first1=Rudolf | last2=Niederreiter | first2=Harald | author2-link=Harald Niederreiter | title=Finite Fields | edition=2nd | year=1997 | publisher=Cambridge University Press | isbn=0-521-39231-4 | url-access=registration | url=https://archive.org/details/finitefields0000lidl_a8r3 }}
• {{SpringerEOM

|title=Galois field

|id=Galois_field&oldid=34238

|author-last1=Skopin

|author-first1=A. I.

}}

{{refend}}

• [http://mathworld.wolfram.com/FiniteField.html Finite Fields] at Wolfram research.
• [https://www.sciencedirect.com/journal/finite-fields-and-their-applications Finite Fields and Their Applications, Science Direct, (Open Access Journal).]

{{Authority control}}

{{DEFAULTSORT:Finite Field}}