Finite field
Encyclopedia
In abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...

, a finite field or Galois field (so named in honor of Évariste Galois
Évariste Galois
Évariste Galois was a French mathematician born in Bourg-la-Reine. While still in his teens, he was able to determine a necessary and sufficient condition for a polynomial to be solvable by radicals, thereby solving a long-standing problem...

) is a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

that contains a finite number of elements. Finite fields are important in number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, algebraic geometry
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...

, Galois theory
Galois theory
In mathematics, more specifically in abstract algebra, Galois theory, named after Évariste Galois, provides a connection between field theory and group theory...

, cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, and coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

. The finite fields are classified by size; there is exactly one finite field up to
Up to
In mathematics, the phrase "up to x" means "disregarding a possible difference in  x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...

isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations.  If there exists an isomorphism between two structures, the two structures are said to be isomorphic.  In a certain sense, isomorphic structures are...

of size pk for each prime p and positive integer k. Each finite field of size q is the splitting field
Splitting field
In abstract algebra, a splitting field of a polynomial with coefficients in a field is a smallest field extension of that field over which the polynomial factors into linear factors.-Definition:...

of the polynomial xq - x, and thus the fixed field of the Frobenius endomorphism
Frobenius endomorphism
In commutative algebra and field theory, the Frobenius endomorphism is a special endomorphism of commutative rings with prime characteristic p, an important class which includes finite fields. The endomorphism maps every element to its pth power...

which takes x to xq. Similarly, the multiplicative group of the field is a cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

. Wedderburn's little theorem
Wedderburn's little theorem
In mathematics, Wedderburn's little theorem states that every finite domain is a field. In other words, for finite rings, there is no distinction between domains, skew-fields and fields.The Artin–Zorn theorem generalizes the theorem to alternative rings....

states that the Brauer group
Brauer group
In mathematics, the Brauer group of a field K is an abelian group whose elements are Morita equivalence classes of central simple algebras of finite rank over K and addition is induced by the tensor product of algebras. It arose out of attempts to classify division algebras over a field and is...

of a finite field is trivial, so that every finite division ring
Division ring
In abstract algebra, a division ring, also called a skew field, is a ring in which division is possible. Specifically, it is a non-trivial ring in which every non-zero element a has a multiplicative inverse, i.e., an element x with...

is a finite field. Finite fields have applications in many areas of mathematics and computer science, including coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

, LFSRs, modular representation theory
Modular representation theory
Modular representation theory is a branch of mathematics, and that part of representation theory that studies linear representations of finite group G over a field K of positive characteristic...

, and the groups of Lie type. Finite fields are an active area of research, including recent results on the Kakeya conjecture and open problems on the size of the smallest primitive root.

Finite fields appear in the following chain of class inclusions:
Commutative ring
Commutative ring
In ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra....

s
integral domainsintegrally closed domain
Integrally closed domain
In commutative algebra, an integrally closed domain A is an integral domain whose integral closure in the field of fractions of A is A itself...

s
unique factorization domain
Unique factorization domain
In mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...

s
principal ideal domain
Principal ideal domain
In abstract algebra, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principal, although some authors refer to PIDs as...

s
Euclidean domain
Euclidean domain
In mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain is a ring that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm...

s
field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

s
finite fields.

## Classification

The finite fields are classified as follows :
• The order, or number of elements, of a finite field is of the form pn, where p is a prime number called the characteristic
Characteristic (algebra)
In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...

of the field, and n is a positive integer.
• For every prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

p and positive integer n, there exists a finite field with pn elements.
• Any two finite fields with the same number of elements are isomorphic. That is, under some renaming of the elements of one of these, both its addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....

and multiplication table
Multiplication table
In mathematics, a multiplication table is a mathematical table used to define a multiplication operation for an algebraic system....

s become identical to the corresponding tables of the other one.

This classification justifies using a naming scheme for finite fields that specifies only the order of the field. One notation for a finite field is Fpn. Another notation is GF(pn), where the letters "GF" stand for "Galois field".

### Examples

First we consider fields where the size is prime, i.e., n = 1. Such a field is also called a Prime field. An example of such a finite field is the ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...

Z/pZ. It is a finite field with p elements, usually labelled 0, 1, 2, ..., p−1, where arithmetic is performed modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

p. It is also sometimes denoted
Zp, but within some areas of mathematics, particularly number theory, this may cause confusion because the same notation Zp is used for the ring of p-adic integers
In mathematics, and chiefly number theory, the p-adic number system for any prime number p extends the ordinary arithmetic of the rational numbers in a way different from the extension of the rational number system to the real and complex number systems...

.

Next we consider fields where the size is not prime, but is a prime power, i.e.,
n > 1.
Two isomorphic constructions of the field with 4 elements are (
Z/2Z)[T]/(T2+T+1) and Z[φ]/(2Z[φ]), where φ = . A field with 8 elements is (Z/2Z)[T]/(T3+T+1). Two isomorphic constructions of the field with 9 elements are (Z/3Z)[T]/(T2+1) and Z[i]/(3Z[i]).

Even though all fields of size
p are isomorphic to Z/pZ,
for n ≥ 2 the ring Z/pnZ (the ring of integers modulo pn) is not a field. The element p (mod pn) is nonzero and has no multiplicative inverse. By comparison with the ring Z/4Z of size 4, the underlying additive group of the field (Z/2Z)[T]/(T2+T+1) of size 4 is not cyclic but rather is isomorphic to the Klein four-group
Klein four-group
In mathematics, the Klein four-group is the group Z2 × Z2, the direct product of two copies of the cyclic group of order 2...

, (Z/2Z)2.

A prime power field with n=2 is also called a binary field.

Finally, we consider fields where the size is not a prime power
Prime power
In mathematics, a prime power is a positive integer power of a prime number.For example: 5=51, 9=32 and 16=24 are prime powers, while6=2×3, 15=3×5 and 36=62=22×32 are not...

. As it turns out, none exist. For example, there is no field with 6 elements, because 6 is not a prime power
Prime power
In mathematics, a prime power is a positive integer power of a prime number.For example: 5=51, 9=32 and 16=24 are prime powers, while6=2×3, 15=3×5 and 36=62=22×32 are not...

. Each and every pair of operations on a set of 6 elements fails to satisfy the mathematical definition of a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

.

### Proof outline

The characteristic of a finite field is a prime p (since a field has no zero divisors), and the field is a vector space of some finite dimension, say n, over Z/pZ, hence the field has pn elements. A field of order p exists, because Fp = Z/pZ is a field, where primality is required for the nonzero elements to have multiplicative inverses.

For any prime power
q = pn, Fq is the splitting field
Splitting field
In abstract algebra, a splitting field of a polynomial with coefficients in a field is a smallest field extension of that field over which the polynomial factors into linear factors.-Definition:...

of the polynomial
f(T) = TqT over
Fp. This field exists and is unique up to isomorphism by the construction of splitting fields. The set of roots is a field, the fixed field of the nth iterate of the Frobenius endomorphism
Frobenius endomorphism
In commutative algebra and field theory, the Frobenius endomorphism is a special endomorphism of commutative rings with prime characteristic p, an important class which includes finite fields. The endomorphism maps every element to its pth power...

, so the splitting field is exactly the
q roots of this polynomial, which are distinct because the polynomial TqT is separable over Fp: its derivative is −1, which has no roots.

#### Order

We give two proofs that a finite field has prime-power order.

For the first proof, let
F be a finite field. Write its additive identity
In mathematics the additive identity of a set which is equipped with the operation of addition is an element which, when added to any element x in the set, yields x...

as 0 and its multiplicative identity as 1. The characteristic of
F is a prime number p as the characteristic of a finite ring is positive and must be prime or else the ring would have zero divisors. The p distinct elements 0, 1, 2, ..., p−1 (where 2 means 1+1, etc.) form a subfield of F that is isomorphic to Z/pZ. F is a vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

over Z/pZ, and it must have finite dimension
Dimension (vector space)
In mathematics, the dimension of a vector space V is the cardinality of a basis of V. It is sometimes called Hamel dimension or algebraic dimension to distinguish it from other types of dimension...

over
Z/
p
Z. Call the dimension n, so each element of F is specified uniquely by n coordinates in Z/pZ. There are p possibilities for each coordinate, with no dependencies among different coordinates, so the number of elements in F is pn. This proves the first statement, and does a little more: it shows that, additively, F is a direct sum of copies of Z/pZ.

For the second proof, which is longer than the one above, we look more closely at the additive structure of a finite field. When F is a finite field and a and b are any two nonzero elements of F, the function f(x) = (b/a)x on F is an additive automorphism which sends a to b. (It certainly is not multiplicative too, in general!) So F is, under addition, a finite abelian group in which any two nonidentity elements are linked by an automorphism.
Let's show that for any nontrivial finite abelian group A where any two nonzero elements are linked by an automorphism of A, the size of A must be a prime power. Let p be a prime factor of the size of A. By Cauchy's theorem, there is an element a of A of order p. Since we are assuming for every nonzero b in A there is an automorphism f of A such that f(a) = b, b must have order p as well. Hence all nonzero elements in A have order p. If q were any prime dividing the size of A, by Cauchy's theorem there is an element in A of order q, and since we have shown all nonzero elements have order p it follows that q = p. Thus p is the only prime factor of the size of A, so A has order equal to a power of p.

Remark: In that group-theoretic argument, one could remove the assumption that A is abelian and directly show A has to be abelian. That is, if G is a nontrivial finite group in which all nonidentity elements are linked by an automorphism, G must be an abelian group of p-power order for some prime p. The prime-power order argument goes as above, and once we know G is a p-group we appeal once again to the automorphism-linking condition, as follows. Since G is a nontrivial finite p-group, it has a nontrivial center. Pick a nonidentity element g in the center. For any h in G, there is an automorphism of G sending g to h, so h has to be in the center too since any automorphism of a group preserves the center. Therefore all elements of G are in its center, so G is abelian.

We can go further with this and show A has to be a direct sum of cyclic groups of order p. From the classification of finite abelian p-groups, A is a direct sum of cyclic groups of p-power order. Since all nonzero elements of A have order p, the cyclic groups in such a direct sum decomposition can't have order larger than p, so they all have order p. Returning to the motivating application where A is F as an additive group, we have recovered the fact that F is a direct sum of copies of Z/pZ (cyclic group of order p).

Now the first proof, using linear algebra, is a lot shorter and is the standard argument found in (nearly) all textbooks that treat finite fields. The second proof is interesting because it gets the same result by working much more heavily with the additive structure of a finite field. Of course we had to use the multiplicative structure
somewhere (after all, not all finite rings have prime-power order), and it was used right at the start: multiplication by b/a on F sends a to b. The second proof is actually the one which was used in E. H. Moore
E. H. Moore
Eliakim Hastings Moore was an American mathematician.-Life:Moore, the son of a Methodist minister and grandson of US Congressman Eliakim H. Moore, discovered mathematics through a summer job at the Cincinnati Observatory while in high school. He learned mathematics at Yale University, where he was...

's 1903 paper which (for the first time) classified all finite fields.

#### Existence

The proof of the second statement, concerning the existence of a finite field of size
q = pn for any prime p and positive integer n, is more involved. We again give two arguments.

The case
n = 1 is easy: take Fp = Z/pZ.

For general n, inside Fp[T] consider the polynomial f(T) = TqT. It is possible to construct a field F (called the splitting field
Splitting field
In abstract algebra, a splitting field of a polynomial with coefficients in a field is a smallest field extension of that field over which the polynomial factors into linear factors.-Definition:...

of f over Fp), which contains Fp and which is large enough for f(T) to split completely into linear factors:
f(T) = (Tr1)(Tr2)⋯(Trq)

in F[T]. The existence of splitting fields in general is discussed in construction of splitting fields. These q roots are distinct, because TqT is a polynomial of degree q which has no repeated roots in F: its derivative
Formal derivative
In mathematics, the formal derivative is an operation on elements of a polynomial ring or a ring of formal power series that mimics the form of the derivative from calculus. Though they appear similar, the algebraic advantage of a formal derivative is that it does not rely on the notion of a...

is qTq−1 − 1, which is −1 (because q = 0 in F) and therefore the derivative has no roots in common with f(T). Furthermore, setting R to be the set of these roots,
R = { r1, ..., rq } = { roots of the equation Tq = T }

one sees that R itself forms a field, as follows. Both 0 and 1 are in R, because 0q = 0 and 1q = 1. If r and s are in R, thenq = rq + sq = r + s
so that r+s is in R. The first equality above follows from the binomial theorem
Binomial theorem
In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the power n into a sum involving terms of the form axbyc, where the exponents b and c are nonnegative integers with , and the coefficient a of...

and the fact that F has characteristic p. Therefore R is closed under addition. Similarly, R is closed under multiplication and taking inverses, because
(rs)q = rq sq = rs

and
(r−1)q = (rq)−1 = r−1.

Therefore R is a field with q elements, proving the second statement.

For the second proof that a field of size q = pn exists, we just sketch the ideas. We will give a combinatorial argument that a monic irreducible f(T) of degree n exists in Fp[T]. Then the quotient ring Fp[T] / (f(T)) is a field of size q. Because TqT has no repeated irreducible factors (it is a separable polynomial in Fp[T]), it is a product of distinct monic irreducibles. We ask: which monic irreducibles occur in the factorization? Using some group theory, one can show that a monic irreducible in Fp[T] is a factor precisely when its degree divides n. Writing Np(d) for the number of monic irreducibles of degree d in Fp[T], computing the degree of the irreducible factorization of TqT shows q = pn is the sum of dNp(d) over all d dividing n. This holds for all n, so by Moebius inversion one can get a formula for Np(n) for all n, and a simple lower bound estimate using this formula shows Np(n) is positive. Thus a (monic) irreducible of degree n in Fp[T] exists, for any n.

#### Uniqueness

Finally the uniqueness statement: a field of size q = pn is the splitting field of Tq - T over its subfield of size p, and for any field K, two splitting fields of a polynomial in K[T] are unique up to isomorphism over K. That is, the two splitting fields are isomorphic by an isomorphism extending the identification of the copies of K inside the two splitting fields.
Since a field of size p can be embedded in a field of characteristic p in only one way (the multiplicative identity 1 in the field is unique, then 2 = 1 + 1, and so on up to p - 1), the condition of two fields of size q being isomorphic over their subfields of size p is the same as just being isomorphic fields.

Warning: it is not the case that two finite fields of the same size are isomorphic in a unique way, unless the fields have size p. Two fields of size pn are isomorphic to each other in n ways (because a field of size pn is isomorphic to itself in n ways, from Galois theory for finite fields).

## Explicitly constructing finite fields

Given a prime power
Prime power
In mathematics, a prime power is a positive integer power of a prime number.For example: 5=51, 9=32 and 16=24 are prime powers, while6=2×3, 15=3×5 and 36=62=22×32 are not...

q = pn, we may explicitly construct a finite field with q elements as follows. Select a monic irreducible polynomial
Irreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....

f(T) of degree n in Fp[T]. (Such a polynomial is guaranteed to exist, once we know that a finite field of size q exists: just take the minimal polynomial
Minimal polynomial (field theory)
In field theory, given a field extension E / F and an element α of E that is an algebraic element over F, the minimal polynomial of α is the monic polynomial p, with coefficients in F, of least degree such that p = 0...

of any primitive element for that field over the subfield Fp.) Then Fp[T]/(f(T)) is a field of size q. Here,
Fp[T] denotes the ring of all polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

s in T with coefficients in Fp, (f(T)) denotes the ideal
Ideal (ring theory)
In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....

generated by f(T), and the quotient is meant in the sense of quotient ring
Quotient ring
In ring theory, a branch of modern algebra, a quotient ring, also known as factor ring or residue class ring, is a construction quite similar to the factor groups of group theory and the quotient spaces of linear algebra...

s — the set of polynomials in T with coefficients in Fp modulo (f(T)).

### Examples

The polynomial f(T) = T 2 + T + 1 is irreducible over Z/2Z, and (Z/2Z)[T] / (T2+T+1) has size 4. Its elements can be written as the set {0, 1, t, t+1} where the multiplication is carried out by using the relation t2 + t + 1 = 0. In fact, since we are working over Z/2Z (that is, in characteristic 2), we may write this as t2 = t + 1. (This follows because −1 = 1 in Z/2Z) Then, for example, to determine t3, we calculate: t3 = t(t2) = t(t+1) = t2+t = t+1+t = 2t + 1 = 1, so t3 = 1.

In order to find the multiplicative inverse of t in this field, we have to find a polynomial p(T) such that T * p(T) = 1 modulo T 2 + T + 1. The polynomial p(T) = T + 1 works, and hence 1/t = t + 1.

To construct a field of size 27, we could start for example with the irreducible polynomial T 3 + T 2 + T + 2 over Z/3Z. The field (Z/3Z)[T]/(T 3 + T 2 + T + 2) has size 27. Its elements have the form at2 + bt + c where a, b, and c lie in Z/3Z and the multiplication is defined by t 3 + t 2 + t + 2 = 0, or by rearranging this equation, t3 = 2t2 + 2t + 1.

### Frobenius automorphisms

If F is a finite field with q = pn elements (where p is prime), then
xq = x

for all x in F (see Analog of Fermat's little theorem below). Furthermore, the map
f : FF

defined by
f(x) = xp

is bijective and a homomorphism
Homomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...

, and is therefore an automorphism
Automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms of an object forms a group, called the automorphism...

on the field F which fixes the subfield with p elements. It is called the Frobenius automorphism, after Ferdinand Georg Frobenius
Ferdinand Georg Frobenius
Ferdinand Georg Frobenius was a German mathematician, best known for his contributions to the theory of differential equations and to group theory...

.

The Frobenius automorphism of a field of size pn has order n, and the cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...

it generates is the full group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

of automorphisms of the field.

### Algebraic closure

Finite fields are not algebraically closed: the polynomial
has no roots over F, as f(α) = 1 for all α in F. However, for each prime p there is an algebraic closure
Algebraic closure
In mathematics, particularly abstract algebra, an algebraic closure of a field K is an algebraic extension of K that is algebraically closed. It is one of many closures in mathematics....

of any finite field of characteristic p, as below.

### Containment

The field Fpn contains a copy of Fpm if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

m divides
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...

n. "Only if" is because the larger field is a vector space over the smaller field, of some finite dimension, say d, so it must have size , so m divides n. "If" is because there exist irreducible polynomials of every degree over Fpm.

The direct limit
Direct limit
In mathematics, a direct limit is a colimit of a "directed family of objects". We will first give the definition for algebraic structures like groups and modules, and then the general definition which can be used in any category.- Algebraic objects :In this section objects are understood to be...

of this system is a field, and is an algebraic closure
Algebraic closure
In mathematics, particularly abstract algebra, an algebraic closure of a field K is an algebraic extension of K that is algebraically closed. It is one of many closures in mathematics....

of Fp (or indeed of Fpn for any n), denoted . This field is infinite, as it is algebraically closed, or more simply because it contains a subfield of size pn for all n.

The inclusions commute with the Frobenius map, as it is defined the same way on each field (it is still just the function raising to the pth power), so the Frobenius map defines an automorphism of , which carries all subfields back to themselves. Unlike in the case of finite fields, the Frobenius automorphism on the algebraic closure of Fp has infinite order (no iterate of it is the identity function on the whole field), and it does not generate the full group of automorphisms of this field. That is, there are automorphisms of the algebraic closure which are not iterates of the pth power map. However, the iterates of the pth power map do form a dense subgroup of the automorphism group in the Krull topology. Algebraically, this corresponds to the additive group Z being dense in the profinite integers (direct product of the p-adic integers over all primes p, with the product topology
Product topology
In topology and related areas of mathematics, a product space is the cartesian product of a family of topological spaces equipped with a natural topology called the product topology...

).

The field Fpn can be recovered as the fixed points of the nth iterate of the Frobenius map.

If we actually construct our finite fields in such a fashion that Fpn is contained in Fpm whenever n divides m, then this direct limit can be constructed as the union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...

of all these fields. Even if we do not construct our fields this way, we can still speak of the algebraic closure, but some more delicacy is required in its construction.

### Irreducibility of polynomials

If F is a finite field, a polynomial f(X) with coefficients in F is said to be irreducible over F if and only if f(X) is irreducible as an element of the polynomial ring
Polynomial ring
In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...

over F (that is, in F[X]). Note that since the polynomial ring F[X] is a unique factorization domain
Unique factorization domain
In mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...

, a polynomial f(X) is irreducible if and only if it is prime as an element of F[X].

There are several fundamental questions one can ask about irreducible polynomials over a given finite field. Firstly, is it possible to give an explicit formula, in the variables q and n, that yields the number of irreducible polynomials over Fq of degree n? Note that since there are only finitely many polynomials of a given degree n over the finite field Fq, there can be only finitely many such irreducible polynomials. However, while little theory is required to compute the number of polynomials of degree n over Fq (there are precisely qn(q−1) such polynomials), it is not immediately obvious how to compute the number of irreducible polynomials of degree n over q.

Secondly, is it possible to describe an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

that may be used to decide whether a given polynomial over Fq is irreducible? In fact, there exists two such (known) algorithms: the Berlekamp algorithm and the Cantor-Zassenhaus algorithm
Cantor-Zassenhaus algorithm
In computational algebra, the Cantor–Zassenhaus algorithm is a well known method for factorising polynomials over finite fields .The algorithm consists mainly of exponentiation and polynomial GCD computations. It was invented by D...

. Furthermore, these algorithms do much more than merely decide whether a given polynomial is irreducible; they may also be implemented to explicitly compute the irreducible factors of f.

#### Number of monic irreducible polynomials of a given degree over a finite field

If Fq denotes the finite field of order q, then the number N of monic irreducible polynomials of degree n over Fq is given by:

where μ is the Möbius function
Möbius function
The classical Möbius function μ is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832...

. By the above formula, the number of irreducible polynomials of degree n over Fq is given by . A (slightly simpler) lower bound on N also exists, and is given by:

### Wedderburn's little theorem

A division ring
Division ring
In abstract algebra, a division ring, also called a skew field, is a ring in which division is possible. Specifically, it is a non-trivial ring in which every non-zero element a has a multiplicative inverse, i.e., an element x with...

is a generalization of field, which are not assumed commutative. There are no non-commutative finite division rings: Wedderburn's little theorem
Wedderburn's little theorem
In mathematics, Wedderburn's little theorem states that every finite domain is a field. In other words, for finite rings, there is no distinction between domains, skew-fields and fields.The Artin–Zorn theorem generalizes the theorem to alternative rings....

states that all finite division ring
Division ring
In abstract algebra, a division ring, also called a skew field, is a ring in which division is possible. Specifically, it is a non-trivial ring in which every non-zero element a has a multiplicative inverse, i.e., an element x with...

s are commutative, hence finite fields. The result holds even if we relax associativity and consider alternative rings, by the Artin–Zorn theorem.

### Cyclic

The multiplicative group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

of every finite field is cyclic, a special case of a theorem mentioned in the article about fields
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

(see Field (mathematics)#Some first theorems).
A generator for the multiplicative group is a primitive element.

This means that if F is a finite field with q elements, then there exists an element x in F such that
F = { 0, 1, x, x2, ..., xq-2 }.

The primitive element x is not unique (unless q = 2 or 3): the set of generators has size where is Euler's totient function
Euler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...

. If we fix a generator, then for any non-zero element a in Fq, there is a unique integer n with
0 ≤ nq − 2

such that
a = xn.

The value of n for a given a is called the discrete log
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

of a (in the given field, to base x).

### Analog of Fermat's little theorem

Every element of a field of size q satisfies aq = a. When q is prime, this is just Fermat's little theorem
Fermat's little theorem
Fermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...

, which states that apa (mod p) for any integer a and prime p.

The general statement for any finite field follows because the non-zero elements in a field of size q form a group under multiplication of order q−1, so by Lagrange's theorem
Lagrange's theorem (group theory)
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....

aq−1 = 1 for any nonzero a in the field. Then aq = a and this holds for 0 as well.

## Applications

Discrete exponentiation, also known as calculating a = xn from x and n, can be computed quickly using techniques of fast exponentiation such as
binary exponentiation
Exponentiation by squaring
Exponentiating by squaring is a general method for fast computation of large integer powers of a number. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add...

, which takes only O(log n) field operations. No fast way of computing the discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

n given a and x is known, and this has many applications in cryptography, such as the Diffie-Hellman protocol.

Finite fields also find applications in coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

: many codes are constructed as subspace
Linear subspace
The concept of a linear subspace is important in linear algebra and related fields of mathematics.A linear subspace is usually called simply a subspace when the context serves to distinguish it from other kinds of subspaces....

s of vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

s over finite fields.

Within number theory, the significance of finite fields is their role in the definition of the Frobenius element (or, more accurately, Frobenius conjugacy class) attached to a prime ideal in a Galois extension of number fields, which in turn is needed to make sense of Artin L-functions of representations of the Galois group, the non-abelian generalization of Dirichlet L-functions.

Counting solutions to equations over finite fields leads into deep questions in algebraic geometry
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...

, the Weil conjectures
Weil conjectures
In mathematics, the Weil conjectures were some highly-influential proposals by on the generating functions derived from counting the number of points on algebraic varieties over finite fields....

, and in fact was the motivation for Grothendieck's development of modern algebraic geometry.

## Some small finite fields

F2
GF(2)
GF is the Galois field of two elements. It is the smallest finite field.- Definition :The two elements are nearly always called 0 and 1, being the additive and multiplicative identities, respectively...

:
EWLINE
+ 0 1
0 0 1
1 1 0
EWLINE
× 0 1
0 0 0
1 0 1

F3:
EWLINE
+ 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
EWLINE
× 0 1 2
0 0 0 0
1 0 1 2
2 0 2 1

F4:
EWLINE
+ 0 1 A B
0 0 1 A B
1 1 0 B A
A A B 0 1
B B A 1 0
EWLINE
× 0 1 A B
0 0 0 0 0
1 0 1 A B
A 0 A B 1
B 0 B 1 A

• Finite field arithmetic
Finite field arithmetic
Arithmetic in a finite field is different from standard integer arithmetic. There are a limited number of elements in the finite field; all operations performed in the finite field result in an element within that field....

• Quasi-finite field
Quasi-finite field
In mathematics, a quasi-finite field is a generalisation of a finite field. Standard local class field theory usually deals with complete valued fields whose residue field is finite In mathematics, a quasi-finite field is a generalisation of a finite field. Standard local class field theory usually...

• Trigonometry in Galois fields
Trigonometry in Galois fields
In mathematics, trigonometry analogies are supported by the theory of quadratic extensions of finite fields, also known as Galois fields. The main motivation to deal with a finite field trigonometry is the power of the discrete transforms, which play an important role in engineering and mathematics...

• Field with one element
Field with one element
In mathematics, the field with one element is a suggestive name for an object that should behave similarly to a finite field with a single element, if such a field could exist. This object is denoted F1, or, in a French-English pun, Fun...