HOME

TheInfoList



OR:

In mathematics, a finite field or Galois field (so-named in honor of
Évariste Galois Évariste Galois (; ; 25 October 1811 – 31 May 1832) was a French mathematician and political activist. While still in his teens, he was able to determine a necessary and sufficient condition for a polynomial to be solvable by radicals, ...
) is a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
that contains a finite number of elements. As with any field, a finite field is a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod when is a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. The ''order'' of a finite field is its number of elements, which is either a prime number or a
prime power In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number. For example: , and are prime powers, while , and are not. The sequence of prime powers begins: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...
. For every prime number and every positive integer there are fields of order p^k, all of which are isomorphic. Finite fields are fundamental in a number of areas of mathematics and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, including
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, algebraic geometry,
Galois theory In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
,
finite geometry Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marke ...
,
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
and
coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied ...
.


Properties

A finite field is a finite set which is a
field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
; 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. The number of elements of a finite field is called its ''order'' or, sometimes, its ''size''. A finite field of order exists if and only if is a
prime power In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number. For example: , and are prime powers, while , and are not. The sequence of prime powers begins: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...
(where is a prime number and is a positive integer). In a field of order , adding copies of any element always results in zero; that is, the characteristic of the field is . If , all fields of order are isomorphic (see 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 \mathbb_, or , where the letters GF stand for "Galois field". In a finite field of order , the
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
has all elements of the finite field as
root In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the su ...
s. The non-zero elements of a finite field form a
multiplicative group In mathematics and group theory, the term multiplicative group refers to one of the following concepts: *the group under multiplication of the invertible elements of a field, ring, or other structure for which one of its operations is referre ...
. This group is
cyclic Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in s ...
, 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 A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
, the
prime field In mathematics, the characteristic of a ring , often denoted , is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive ide ...
of order , \mathbb_, may be constructed as the integers modulo , . The elements of the prime field of order may be represented by integers in the range . The sum, the difference and the product are the remainder of the division by of the result of the corresponding integer operation. The multiplicative inverse of an element may be computed by using the extended Euclidean algorithm (see ). Let be a finite field. For any element in and any
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
, denote by the sum of copies of . The least positive such that is the characteristic of the field. This allows defining a multiplication (k,x) \mapsto k \cdot x of an element of by an element of by choosing an integer representative for . This multiplication makes into a -
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
. It follows that the number of elements of is for some integer . The
identity Identity may refer to: * Identity document * Identity (philosophy) * Identity (social science) * Identity (mathematics) Arts and entertainment Film and television * ''Identity'' (1987 film), an Iranian film * ''Identity'' (2003 film), ...
(x+y)^p=x^p+y^p (sometimes called the
freshman's dream The freshman's dream is a name sometimes given to the erroneous equation (x+y)^n=x^n+y^n, where n is a real number (usually a positive integer greater than 1) and x,y are nonzero real numbers. Beginning students commonly make this error in computi ...
) is true in a field of characteristic . This follows from the
binomial theorem In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial into a sum involving terms of the form , where the ...
, as each binomial coefficient of the expansion of , except the first and the last, is a multiple of . By Fermat's little theorem, if is a prime number and is in the field then . This implies the equality X^p-X=\prod_ (X-a) for polynomials over . More generally, every element in satisfies the polynomial equation . Any finite field extension of a finite field is separable and simple. That is, if is a finite field and is a subfield of , then is obtained from by adjoining a single element whose minimal polynomial is separable. To use a 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 In algebra, a division ring, also called a skew field, is a nontrivial ring in which division by nonzero elements is defined. Specifically, it is a nontrivial ring in which every nonzero element has a multiplicative inverse, that is, an element ...
(or sometimes ''skew field''). By
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, division rings and fields. The Artin–Zorn theorem generalizes the theorem to al ...
, any finite division ring is commutative, and hence is a finite field.


Existence and uniqueness

Let be a
prime power In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number. For example: , and are prime powers, while , and are not. The sequence of prime powers begins: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...
, and be the
splitting field In abstract algebra, a splitting field of a polynomial with coefficients in a field is the smallest field extension of that field over which the polynomial ''splits'', i.e., decomposes into linear factors. Definition A splitting field of a poly ...
of the polynomial P = X^q-X over the prime field . This means that is a finite field of lowest order, in which has distinct roots (the formal derivative of is , implying that , which in general implies that the splitting field is a
separable extension In field theory, a branch of algebra, an algebraic field extension E/F is called a separable extension if for every \alpha\in E, the minimal polynomial of \alpha over is a separable polynomial (i.e., its formal derivative is not the zero polyno ...
of the original). The above identity shows that the sum and the product of two roots of are roots of , as well as the multiplicative inverse of a root of . In other words, the roots of form a field of order , which is equal to by the minimality of the splitting field. The uniqueness up to isomorphism of splitting fields implies thus that all fields of order are isomorphic. Also, if a field has a field of order as a subfield, its elements are the roots of , and cannot contain another subfield of order . In summary, we have the following classification theorem first proved in 1893 by
E. H. Moore Eliakim Hastings Moore (; January 26, 1862 – December 30, 1932), usually cited as E. H. Moore or E. Hastings Moore, was an American mathematician. Life Moore, the son of a Methodist minister and grandson of US Congressman Eliakim H. Moore, di ...
:
''The order of a finite field is a prime power. For every prime power'' ''there are fields of order'' , ''and they are all isomorphic. In these fields, every element satisfies'' x^q=x, ''and the polynomial'' ''factors as'' X^q-X= \prod_ (X-a).
It follows that contains a subfield isomorphic to if and only if is a divisor of ; in that case, this subfield is unique. In fact, the polynomial divides if and only if is a divisor of .


Explicit construction


Non-prime fields

Given a prime power with prime and , the field may be explicitly constructed in the following way. One first chooses an
irreducible polynomial In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted f ...
in of degree (such an irreducible polynomial always exists). Then the
quotient ring In ring theory, a branch of abstract algebra, a quotient ring, also known as factor ring, difference ring or residue class ring, is a construction quite similar to the quotient group in group theory and to the quotient space in linear algebra. ...
\mathrm(q) = \mathrm(p) (P) of the polynomial ring by the ideal generated by is a field of order . More explicitly, the elements of are the polynomials over whose degree is strictly less than . The addition and the subtraction are those of polynomials over . The product of two elements is the remainder of the
Euclidean division In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
by of the product in . The multiplicative inverse of a non-zero element may be computed with the extended Euclidean algorithm; see Extended Euclidean algorithm § Simple algebraic field extensions. Except in the construction of , there are several possible choices for , which produce isomorphic results. To simplify the Euclidean division, one commonly chooses for a polynomial of the form X^n + aX + b, which make the needed Euclidean divisions very efficient. However, for some fields, typically in characteristic , irreducible polynomials of the form may not exist. In characteristic , if the polynomial is reducible, it is recommended to choose with the lowest possible that makes the polynomial irreducible. If all these
trinomial In elementary algebra, a trinomial is a polynomial consisting of three terms or monomials. Examples of trinomial expressions # 3x + 5y + 8z with x, y, z variables # 3t + 9s^2 + 3y^3 with t, s, y variables # 3ts + 9t + 5s with t, s variables # ...
s are reducible, one chooses "pentanomials" , as polynomials of degree greater than , with an even number of terms, are never irreducible in characteristic , having as a root. 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.


Field with four elements

The smallest non-prime field is the field with four elements, which is commonly denoted or \mathbb F_4. It consists of the four elements 0, 1, \alpha, 1+\alpha such that \alpha^2=1+\alpha, 1\cdot\alpha = \alpha \cdot 1 = \alpha, x+x=0, and x\cdot 0=0\cdot x=0, for every x\in \operatorname(4), the other operation results being easily deduced from the
distributive law In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmetic, ...
. See below for the complete operation tables. This may be deduced as follows from the results of the preceding section. Over , there is only one
irreducible polynomial In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted f ...
of degree : X^2+X+1 Therefore, for the construction of the preceding section must involve this polynomial, and \mathrm(4) = \mathrm(2) (X^2+X+1). Let denote a root of this polynomial in . This implies that and that and are the elements of that are not in . The tables of the operations in 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 by , the values of must be read in the left column, and the values of in the top row. (Because for every in every
ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...
the division by 0 has to remain undefined.) From the tables, it can be see that the additive structure of is isomorphic to the
Klein four-group In mathematics, the Klein four-group is a group with four elements, in which each element is self-inverse (composing it with itself produces the identity) and in which composing any two of the three non-identity elements produces the third one. ...
, while the non-zero multiplicative structure is isomorphic to Z3. The map \varphi:x \mapsto x^2 is the non-trivial field automorphism, called
Frobenius automorphism In commutative algebra and field theory, the Frobenius endomorphism (after Ferdinand Georg Frobenius) is a special endomorphism of commutative rings with prime characteristic , an important class which includes finite fields. The endomorphism m ...
, which sends into the second root of the above mentioned irreducible polynomial X^2+X+1.


GF(''p''2) for an odd prime ''p''

For applying the above general construction of finite fields in the case of , one has to find an irreducible polynomial of degree 2. For , this has been done in the preceding section. If is an odd prime, there are always irreducible polynomials of the form , with in . More precisely, the polynomial is irreducible over if and only if is a
quadratic non-residue In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic no ...
modulo (this is almost the definition of a quadratic non-residue). There are quadratic non-residues modulo . For example, is a quadratic non-residue for , and is a quadratic non-residue for . If , that is , one may choose as a quadratic non-residue, which allows us to have a very simple irreducible polynomial . Having chosen a quadratic non-residue , let be a symbolic square root of , that is a symbol which has the property , in the same way as the complex number is a symbolic square root of . Then, the elements of are all the linear expressions a+b\alpha, with and in . The operations on are defined as follows (the operations between elements of represented by Latin letters are the operations in ): \begin -(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)^&=a(a^2-rb^2)^+(-b)(a^2-rb^2)^\alpha \end


GF(8) and GF(27)

The polynomial X^3-X-1 is irreducible over and , that is, it is irreducible modulo and (to show this, it suffices to show that it has no root in nor in ). It follows that the elements of and may be represented by expressions a+b\alpha+c\alpha^2, where are elements of or (respectively), and \alpha is a symbol such that \alpha^3=\alpha+1. The addition, additive inverse and multiplication on and may thus be defined as follows; in following formulas, the operations between elements of or , represented by Latin letters, are the operations in or , respectively: \begin -(a+b\alpha+c\alpha^2)&=-a+(-b)\alpha+(-c)\alpha^2 \qquad\text \mathrm(8), \text\\ (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


GF(16)

The polynomial X^4+X+1 is irreducible over , that is, it is irreducible modulo . It follows that the elements of may be represented by expressions a+b\alpha+c\alpha^2+d\alpha^3, where are either or (elements of ), and is a symbol such that \alpha^4=\alpha+1 (that is, is defined as a root of the given irreducible polynomial). As the characteristic of is , each element is its additive inverse in . The addition and multiplication on may be defined as follows; in following formulas, the operations between elements of , represented by Latin letters are the operations in . \begin (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 The field has eight primitive elements (the elements that have all nonzero elements of as integer powers). These elements are the four roots of X^4+X+1 and their
multiplicative inverse In mathematics, a multiplicative inverse or reciprocal for a number ''x'', denoted by 1/''x'' or ''x''−1, is a number which when multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a fraction ''a''/ ...
s. In particular, is a primitive element, and the primitive elements are \alpha^m with less than and coprime with 15 (that is, 1, 2, 4, 7, 8, 11, 13, 14).


Multiplicative structure

The set of non-zero elements in is an
abelian group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is comm ...
under the multiplication, of order . By Lagrange's theorem, there exists a divisor of such that for every non-zero in . As the equation has at most solutions in any field, is the highest possible value for . The structure theorem of finite abelian groups implies that this multiplicative group is
cyclic Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in s ...
, that is, all non-zero elements are powers of a single element. In summary: Such an element is called a primitive element. Unless , the primitive element is not unique. The number of primitive elements is where is Euler's totient function. The result above implies that for every in . The particular case where is prime is Fermat's little theorem.


Discrete logarithm

If is a primitive element in , then for any non-zero element in , there is a unique integer with such that This integer is called the discrete logarithm of to the base . While can be computed very quickly, for example using
exponentiation by squaring Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
, there is no known efficient algorithm for computing the inverse operation, the discrete logarithm. This has been used in various
cryptographic protocol A security protocol (cryptographic protocol or encryption protocol) is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods, often as sequences of cryptographic primitives. A protocol descr ...
s, see Discrete logarithm for details. When the nonzero elements of are represented by their discrete logarithms, multiplication and division are easy, as they reduce to addition and subtraction modulo . However, addition amounts to computing the discrete logarithm of . The identity allows one to solve this problem by constructing the table of the discrete logarithms of , called
Zech's logarithm Zech logarithms are used to implement addition in finite fields when elements are represented as powers of a generator \alpha. Zech logarithms are named after Julius Zech, and are also called Jacobi logarithms, after Carl G. J. Jacobi who used ...
s, for (it is convenient to define the discrete logarithm of zero as being ). Zech's logarithms are useful for large computations, such as
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices ...
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.


Roots of unity

Every nonzero element of a finite field is a
root of unity In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important ...
, as for every nonzero element of . If is a positive integer, an -th primitive root of unity is a solution of the equation that is not a solution of the equation for any positive integer . If is a th primitive root of unity in a field , then contains all the roots of unity, which are . The field contains a th primitive root of unity if and only if is a divisor of ; if is a divisor of , then the number of primitive th roots of unity in is ( Euler's totient function). The number of th roots of unity in is . In a field of characteristic , every th root of unity is also a th root of unity. It follows that primitive th roots of unity never exist in a field of characteristic . On the other hand, if is
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to , the roots of the th cyclotomic polynomial are distinct in every field of characteristic , as this polynomial is a divisor of , whose discriminant is nonzero modulo . It follows that the th cyclotomic polynomial factors over into distinct irreducible polynomials that have all the same degree, say , and that is the smallest field of characteristic that contains the th primitive roots of unity.


Example: GF(64)

The field 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 over ) are primitive elements; and the primitive elements are not all conjugate under the
Galois group In mathematics, in the area of abstract algebra known as Galois theory, the Galois group of a certain type of field extension is a specific group associated with the field extension. The study of field extensions and their relationship to the po ...
. The order of this field being , and the divisors of being , the subfields of are , , , and itself. As and are
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
, the intersection of and in is the prime field . The union of and has thus elements. The remaining elements of generate in the sense that no other subfield contains any of them. It follows that they are roots of irreducible polynomials of degree over . This implies that, over , there are exactly irreducible monic polynomials of degree . This may be verified by factoring over . The elements of are primitive th roots of unity for some dividing . As the 3rd and the 7th roots of unity belong to and , respectively, the generators are primitive th roots of unity for some in . Euler's totient function shows that there are primitive th roots of unity, primitive st roots of unity, and primitive rd roots of unity. Summing these numbers, one finds again elements. By factoring the cyclotomic polynomials over , one finds that: * The six primitive 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 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 Reciprocal may refer to: In mathematics * Multiplicative inverse, in mathematics, the number 1/''x'', which multiplied by ''x'' gives the product 1, also known as a ''reciprocal'' * Reciprocal polynomial, a polynomial obtained from another pol ...
to each other, a root and its (multiplicative) inverse do not belong to the same orbit. * The primitive elements of 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 is to define it as . In fact, this generator is a primitive element, and this polynomial is the irreducible polynomial that produces the easiest Euclidean division.


Frobenius automorphism and Galois theory

In this section, is a prime number, and is a power of . In , the identity implies that the map \varphi:x \mapsto x^p is a - linear endomorphism and a
field 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 , which fixes every element of the subfield . It is called the
Frobenius automorphism In commutative algebra and field theory, the Frobenius endomorphism (after Ferdinand Georg Frobenius) is a special endomorphism of commutative rings with prime characteristic , an important class which includes finite fields. The endomorphism m ...
, after Ferdinand Georg Frobenius. Denoting by the
composition Composition or Compositions may refer to: Arts and literature *Composition (dance), practice and teaching of choreography *Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
of with itself times, we have \varphi^k:x \mapsto x^. It has been shown in the preceding section that is the identity. For , the automorphism is not the identity, as, otherwise, the polynomial X^-X would have more than roots. There are no other -automorphisms of . In other words, has exactly -automorphisms, which are \mathrm=\varphi^0, \varphi, \varphi^2, \ldots, \varphi^. In terms of
Galois theory In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
, this means that is a
Galois extension In mathematics, a Galois extension is an algebraic field extension ''E''/''F'' that is normal and separable; or equivalently, ''E''/''F'' is algebraic, and the field fixed by the automorphism group Aut(''E''/''F'') is precisely the base field ' ...
of , which has a
cyclic Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in s ...
Galois group. The fact that the Frobenius map is surjective implies that every finite field is perfect.


Polynomial factorization

If is a finite field, a non-constant
monic polynomial In algebra, a monic polynomial is a single-variable polynomial (that is, a univariate polynomial) in which the leading coefficient (the nonzero coefficient of highest degree) is equal to 1. Therefore, a monic polynomial has the form: :x^n+c_x^+\c ...
with coefficients in is
irreducible In philosophy, systems theory, science, and art, emergence occurs when an entity is observed to have properties its parts do not have on their own, properties or behaviors that emerge only when the parts interact in a wider whole. Emergence ...
over , if it is not the product of two non-constant monic polynomials, with coefficients in . As every
polynomial ring In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables ...
over a field is a
unique factorization domain In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
, 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 field. They are a key step for factoring polynomials over the integers or the
rational numbers In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
. At least for this reason, every
computer algebra system A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The d ...
has functions for factoring polynomials over finite fields, or, at least, over finite prime fields.


Irreducible polynomials of a given degree

The polynomial X^q-X factors into linear factors over a field of order . More precisely, this polynomial is the product of all monic polynomials of degree one over a field of order . This implies that, if then is the product of all monic irreducible polynomials over , whose degree divides . In fact, if is an irreducible factor over of , its degree divides , as its
splitting field In abstract algebra, a splitting field of a polynomial with coefficients in a field is the smallest field extension of that field over which the polynomial ''splits'', i.e., decomposes into linear factors. Definition A splitting field of a poly ...
is contained in . Conversely, if is an irreducible monic polynomial over of degree dividing , it defines a field extension of degree , which is contained in , and all roots of belong to , and are roots of ; thus divides . As 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 ; see Distinct degree factorization.


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

The number of monic irreducible polynomials of degree over is given by N(q,n)=\frac\sum_ \mu(d)q^, where is the
Möbius function The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most of ...
. This formula is almost a direct consequence of the property of above. By the above formula, the number of irreducible (not necessarily monic) polynomials of degree over is . The exact formula implies the inequality N(q,n)\geq\frac \left(q^n-\sum_ q^\right); this is sharp if and only if is a power of some prime. For every and every , the right hand side is positive, so there is at least one irreducible polynomial of degree over .


Applications

In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, the difficulty of the
discrete logarithm problem In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
in finite fields or in
elliptic curves In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If t ...
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. In
coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied ...
, many codes are constructed as subspaces of
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
s over finite fields. Finite fields are used by many error correction codes, such as Reed–Solomon error correction code or
BCH code In coding theory, the Bose–Chaudhuri–Hocquenghem codes (BCH codes) form a class of cyclic error-correcting codes that are constructed using polynomials over a finite field (also called ''Galois field''). BCH codes were invented in 1959 ...
. The finite field almost always has characteristic of 2, since computer data is stored in binary. For example, a byte of data can be interpreted as an element of GF(2^8). One exception is
PDF417 PDF417 is a stacked linear barcode format used in a variety of applications such as transport, identification cards, and inventory management. "PDF" stands for Portable Data File. The "417" signifies that each pattern in the code consists of 4 ...
bar code, which is GF(929). Some CPUs have special instructions that can be useful for finite fields of characteristic 2, generally variations of carry-less product. Finite fields are widely used in
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, as many problems over the integers may be solved by reducing them modulo one or several
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s. For example, the fastest known algorithms for
polynomial factorization In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same dom ...
and
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices ...
over the field of
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
s proceed by reduction modulo one or several primes, and then reconstruction of the solution by using Chinese remainder theorem,
Hensel lifting In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number , then this root can be ''lifted'' to ...
or the
LLL algorithm LLL may refer to: Businesses and organisations *L3 Technologies, an American defense contractor formerly with the NYSE stock symbol LLL *La Leche League, an organization that promotes breastfeeding Education * LL.L (''Legum Licentiatus''), a ...
. 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 In mathematics, Helmut Hasse's local–global principle, also known as the Hasse principle, is the idea that one can find an integer solution to an equation by using the Chinese remainder theorem to piece together solutions modulo powers of eac ...
. 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 Wiles's proof of Fermat's Last Theorem is a proof by British mathematician Andrew Wiles of a special case of the modularity theorem for elliptic curves. Together with Ribet's theorem, it provides a proof for Fermat's Last Theorem. Both Fermat's ...
is an example of a deep result involving many mathematical tools, including finite fields. The
Weil conjectures In mathematics, the Weil conjectures were highly influential proposals by . They led to a successful multi-decade program to prove them, in which many leading researchers developed the framework of modern algebraic geometry and number theory. Th ...
concern the number of points on
algebraic varieties Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. ...
over finite fields and the theory has many applications including
exponential Exponential may refer to any of several mathematical topics related to exponentiation, including: *Exponential function, also: **Matrix exponential, the matrix analogue to the above *Exponential decay, decrease at a rate proportional to value *Expo ...
and
character sum In mathematics, a character sum is a sum \sum \chi(n) of values of a Dirichlet character χ '' modulo'' ''N'', taken over a given range of values of ''n''. Such sums are basic in a number of questions, for example in the distribution of quadratic ...
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 mathematics, a Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. In geometric terms, this means that each pair of rows in ...
. In
arithmetic combinatorics In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis. Scope Arithmetic combinatorics is about combinatorial estimates associated with arithmetic operations (ad ...
finite fields and finite field models are used extensively, such as in
Szemerédi's theorem In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers ''A'' with positive natural density contains a ''k''-ter ...
on arithmetic progressions.


Extensions


Algebraic closure

A finite field is not algebraically closed: the polynomial f(T) = 1+\prod_ (T-\alpha), has no roots in , since for all in . Fix an
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. Using Zorn's lemmaMcCarthy (1991) p.21Kaplansky ( ...
\overline_q of \mathbb_q. The map \varphi_q \colon \overline_q \to \overline_q sending each to is called the th power
Frobenius automorphism In commutative algebra and field theory, the Frobenius endomorphism (after Ferdinand Georg Frobenius) is a special endomorphism of commutative rings with prime characteristic , an important class which includes finite fields. The endomorphism m ...
. The subfield of \overline_q fixed by the th iterate of \varphi_q is the set of zeros of the polynomial , which has distinct roots since its derivative in \mathbb_q /math> is , which is never zero. Therefore that subfield has elements, so it is the unique copy of \mathbb_ in \overline_q. Every finite extension of \mathbb_q in \overline_q is this \mathbb_ for some , so \overline_q = \bigcup_ \mathbb_. The
absolute Galois group In mathematics, the absolute Galois group ''GK'' of a field ''K'' is the Galois group of ''K''sep over ''K'', where ''K''sep is a separable closure of ''K''. Alternatively it is the group of all automorphisms of the algebraic closure of ''K'' t ...
of \mathbb_q is the profinite group \operatorname(\overline_q/\mathbb_q) \simeq \varprojlim_n \operatorname(\mathbb_/\mathbb_q) \simeq \varprojlim_n (\mathbf/n\mathbf) = \widehat. Like any infinite Galois group, \operatorname(\overline_q/\mathbb_q) may be equipped with the
Krull topology In mathematics, a profinite group is a topological group that is in a certain sense assembled from a system of finite groups. The idea of using a profinite group is to provide a "uniform", or "synoptic", view of an entire system of finite groups. ...
, and then the isomorphisms just given are isomorphisms of
topological group In mathematics, topological groups are logically the combination of groups and topological spaces, i.e. they are groups and topological spaces at the same time, such that the continuity condition for the group operations connects these two st ...
s. The image of \varphi_q in the group \operatorname(\mathbb_/\mathbb_q) \simeq \mathbf/n\mathbf is the generator , so \varphi_q corresponds to 1 \in \widehat. It follows that \varphi_q has infinite order and generates a dense subgroup of \operatorname(\overline_q/\mathbb_q), not the whole group, because the element 1 \in \widehat has infinite order and generates the dense subgroup \mathbf \subsetneqq \widehat. One says that \varphi_q is a topological generator of \operatorname(\overline_q/\mathbb_q).


Quasi-algebraic closure

Although finite fields are not algebraically closed, they are
quasi-algebraically closed In mathematics, a field ''F'' is called quasi-algebraically closed (or C1) if every non-constant homogeneous polynomial ''P'' over ''F'' has a non-trivial zero provided the number of its variables is more than its degree. The idea of quasi-algebra ...
, which means that every
homogeneous polynomial In mathematics, a homogeneous polynomial, sometimes called quantic in older texts, is a polynomial whose nonzero terms all have the same degree. For example, x^5 + 2 x^3 y^2 + 9 x y^4 is a homogeneous polynomial of degree 5, in two variables; ...
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 Artin may refer to: * Artin (name), a surname and given name, including a list of people with the name ** Artin, a variant of Harutyun, an Armenian given name * 15378 Artin, a main-belt asteroid See also

{{disambiguation, surname ...
and Dickson proved by Chevalley (see Chevalley–Warning theorem).


Wedderburn's little theorem

A
division ring In algebra, a division ring, also called a skew field, is a nontrivial ring in which division by nonzero elements is defined. Specifically, it is a nontrivial ring in which every nonzero element has a multiplicative inverse, that is, an element ...
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 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, division rings and fields. The Artin–Zorn theorem generalizes the theorem to al ...
states that all finite
division ring In algebra, a division ring, also called a skew field, is a nontrivial ring in which division by nonzero elements is defined. Specifically, it is a nontrivial ring in which every nonzero element has a multiplicative inverse, that is, an element ...
s are commutative, and hence are finite fields. This result holds even if we relax the
associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
axiom to
alternativity In abstract algebra, alternativity is a property of a binary operation. A magma ''G'' is said to be if (xx)y = x(xy) for all x, y \in G and if y(xx) = (yx)x for all x, y \in G. A magma that is both left and right alternative is said to be () ...
, that is, all finite
alternative division ring In abstract algebra, an alternative algebra is an algebra in which multiplication need not be associative, only alternative. That is, one must have *x(xy) = (xx)y *(yx)x = y(xx) for all ''x'' and ''y'' in the algebra. Every associative algebra is ...
s are finite fields, by the
Artin–Zorn theorem In mathematics, the Artin–Zorn theorem, named after Emil Artin and Max Zorn, states that any finite alternative division ring is necessarily a finite field. It was first published in 1930 by Zorn, but in his publication Zorn credited it to Artin. ...
.


See also

* Quasi-finite field *
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. The name ...
*
Finite field arithmetic In mathematics, finite field arithmetic is arithmetic in a finite field (a field containing a finite number of elements) contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers. There are infin ...
*
Finite ring In mathematics, more specifically abstract algebra, a finite ring is a ring that has a finite number of elements. Every finite field is an example of a finite ring, and the additive part of every finite ring is an example of an abelian finite grou ...
* Finite group *
Elementary abelian group In mathematics, specifically in group theory, an elementary abelian group (or elementary abelian ''p''-group) is an abelian group in which every nontrivial element has order ''p''. The number ''p'' must be prime, and the elementary abelian grou ...
*
Hamming space In statistics and coding theory, a Hamming space (named after American mathematician Richard Hamming) is usually the set of all 2^N binary strings of length ''N''. It is used in the theory of coding signals and transmission. More generally, a Ham ...


Notes


References

* W. H. Bussey (1905) "Galois field tables for ''p''''n'' ≤ 169",
Bulletin of the American Mathematical Society The ''Bulletin of the American Mathematical Society'' is a quarterly mathematical journal published by the American Mathematical Society. Scope It publishes surveys on contemporary research topics, written at a level accessible to non-experts. I ...
12(1): 22–38, * W. H. Bussey (1910) "Tables of Galois fields of order < 1000", ''Bulletin of the American Mathematical Society'' 16(4): 188–206, * * * * *


External links


Finite Fields
at Wolfram research. {{DEFAULTSORT:Finite Field