"}},"i":0}}]}" id="mwAvc">{9, 21, 63}. Euler's totient function shows that there are 6 primitive 9th roots of unity, 12 primitive 21st roots of unity, and 36 primitive 63rd roots of unity. Summing these numbers, one finds again 54 elements.
By factoring the cyclotomic polynomials over GF(2), one finds that:
This shows that the best choice to construct GF(64) is to define it as GF(2)[X] / (X^{6} + X + 1). In fact, this generator is a primitive element, and this polynomial is the irreducible polynomial that produces the easiest Euclidean division.
In this section, p is a prime number, and q = p^{n} is a power of p.
In GF(q), the identity (x + y)^{p} = x^{p} + y^{p} implies that the map
is a GF(p)-linear endomorphism and a field automorphism of GF(q), which fixes every element of the subfield GF(p). It is called the Frobenius automorphism, after Ferdinand Georg Frobenius.
Denoting by φ^{k} the composition of φ with itself k times, we have
It has been shown in the preceding section that φ^{n} is the identity. For 0 < k < n, the automorphism φ^{k} is not the identity, as, otherwise, the polynomial
would have more than p^{k} roots.
There are no other GF(p)-automorphisms of GF(q). In other words, GF(p^{n}) has exactly nGF(p)-automorphisms, which are
In terms of Galois theory, this means that GF(p^{n}) is a Galois extension of GF(p), which has a cyclic Galois group.
The fact that the Frobenius map is surjective implies that every finite field is perfect.
If F is a finite field, a non-constant monic polynomial with coefficients in F is irreducible over F, if it is not the product of two non-constant monic polynomials, with coefficients in F.
As every polynomial ring over a field is a unique factorization domain, every monic polynomial over a finite field may be factored in a unique way (up to the order of the factors) into a product of irreducible monic polynomials.
There are efficient algorithms for testing polynomial irreducibility and factoring polynomials over finite field. They are a key step for factoring polynomials over the integers or the rational numbers. At least for this reason, every computer algebra system has functions for factoring polynomials over finite fields, or, at least, over finite prime fields.
The polynomial
factors into linear factors over a field of order q. More precisely, this polynomial is the product of all monic polynomials of degree one over a field of order q.
This implies that, if q = p^{n} then X^{q} − X is the product of all monic irreducible polynomials over GF(p), whose degree divides n. In fact, if P is an irreducible factor over GF(p) of X^{q} − X, its degree divides n, as its splitting field is contained in GF(p^{n}). Conversely, if P is an irreducible monic polynomial over GF(p) of degree d dividing n, it defines a field extension of degree d, which is contained in GF(p^{n}), and all roots of P belong to GF(p^{n}), and are roots of X^{q} − X; thus P divides X^{q} − X. As X^{q} − X does not have any multiple factor, it is thus the product of all the irreducible monic polynomials that divide it.
This property is used to compute the product of the irreducible factors of each degree of polynomials over GF(p); see Distinct degree factorization.
The number N(q, n) of monic irreducible polynomials of degree n over GF(q) is given by^{ [4] }
where μ is the Möbius function. This formula is almost a direct consequence of above property of X^{q} − X.
By the above formula, the number of irreducible (not necessarily monic) polynomials of degree n over GF(q) is (q − 1)N(q, n).
A (slightly simpler) lower bound for N(q, n) is
One may easily deduce that, for every q and every n, there is at least one irreducible polynomial of degree n over GF(q). This lower bound is sharp for q = n = 2.
In cryptography, the difficulty of the discrete logarithm problem in finite fields or in elliptic curves is the basis of several widely used protocols, such as the Diffie–Hellman protocol. For example, in 2014, a secure internet connection to Wikipedia involved the elliptic curve Diffie–Hellman protocol (ECDHE) over a large finite field.^{ [5] } In coding theory, many codes are constructed as subspaces of vector spaces over finite fields.
Finite fields are widely used in number theory, as many problems over the integers may be solved by reducing them modulo one or several prime numbers. For example, the fastest known algorithms for polynomial factorization and linear algebra over the field of rational numbers proceed by reduction modulo one or several primes, and then reconstruction of the solution by using Chinese remainder theorem, Hensel lifting or the LLL algorithm.
Similarly many theoretical problems in number theory can be solved by considering their reductions modulo some or all prime numbers. See, for example, Hasse principle. Many recent developments of algebraic geometry were motivated by the need to enlarge the power of these modular methods. Wiles' proof of Fermat's Last Theorem is an example of a deep result involving many mathematical tools, including finite fields.
The Weil conjectures concern the number of points on algebraic varieties over finite fields and the theory has many applications including exponential and character sum estimates.
Finite fields have widespread application in combinatorics, two well known examples being the definition of Paley Graphs and the related construction for Hadamard Matrices. In arithmetic combinatorics finite fields^{ [6] } and finite field models^{ [7] }^{ [8] } are used extensively, such as in Szemerédi's theorem on arithmetic progressions.
A finite field F is not algebraically closed: the polynomial
has no roots in F, since f (α) = 1 for all α in F.
Fix an algebraic closure of . The map sending each x to x^{q} is called the qth power Frobenius automorphism. The subfield of fixed by the nth iterate of is the set of zeros of the polynomial x^{qn} − x, which has distinct roots since its derivative in is −1, which is never zero. Therefore that subfield has q^{n} elements, so it is the unique copy of in . Every finite extension of in is this for some n, so
The absolute Galois group of is the profinite group
Like any infinite Galois group, may be equipped with the Krull topology, and then the isomorphisms just given are isomorphisms of topological groups. The image of in the group is the generator 1, so corresponds to . It follows that has infinite order and generates a dense subgroup of , not the whole group, because the element has infinite order and generates the dense subgroup One says that is a topological generator of .
Although finite fields are not algebraically closed, they are quasi-algebraically closed, which means that every homogeneous polynomial over a finite field has a non-trivial zero whose components are in the field if the number of its variables is more than its degree. This was a conjecture of Artin and Dickson proved by Chevalley (see Chevalley–Warning theorem).
A division ring is a generalization of field. Division rings are not assumed to be commutative. There are no non-commutative finite division rings: Wedderburn's little theorem states that all finite division rings are commutative, hence finite fields. The result holds even if we relax associativity and consider alternative rings, by the Artin–Zorn theorem.^{ [9] }
In mathematics, particularly in algebra, a field extension is a pair of fields such that the operations of E are those of F restricted to E. In this case, F is an extension field of E and E is a subfield of F. For example, under the usual notions of addition and multiplication, the complex numbers are an extension field of the real numbers; the real numbers are a subfield of the complex numbers.
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 polynomials that give rise to them via Galois groups is called Galois theory, so named in honor of Évariste Galois who first discovered them.
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 n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.
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 or decomposes into linear factors.
Field theory is the branch of mathematics in which fields are studied. This is a glossary of some terms of the subject.
In field theory, a subfield of algebra, an algebraic field extension is called a separable extension if for every , the minimal polynomial of over F is a separable polynomial. There is also a more general definition that applies when E is not necessarily algebraic over F. An extension that is not separable is said to be inseparable.
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.
In field theory, the primitive element theorem is a result characterizing the finite degree field extensions that can be generated by a single element. Such a generating element is called a primitive element of the field extension, and the extension is called a simple extension in this case. The theorem states that a finite extension is simple if and only if there are only finitely many intermediate fields. An older result, also often called "primitive element theorem", states that every finite separable extension is simple; it can be seen as a consequence of the former theorem. These theorems imply in particular that all algebraic number fields over the rational numbers, and all extensions in which both fields are finite, are simple.
In mathematics, the (field) norm is a particular mapping defined in field theory, which maps elements of a larger field into a subfield.
In mathematics, the field trace is a particular function defined with respect to a finite field extension L/K, which is a K-linear map from L onto K.
In mathematics, finite field arithmetic is arithmetic in a finite field contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.
In abstract algebra, a normal extension is an algebraic field extension L/K for which every polynomial that is irreducible over K either has no root in L or splits into linear factors in L. Bourbaki calls such an extension a quasi-Galois extension.
In mathematics, specifically the algebraic theory of fields, a normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory.
In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field GF(p^{m}). In other words, a polynomial F(X) with coefficients in GF(p) = Z/pZ is a primitive polynomial if its degree is m and it has a root α in GF(p^{m}) such that {0, 1, α, α^{2}, α^{3}, ..., α^{pm−2}} is the entire field GF(p^{m}). This means also that α is a primitive -root of unity in GF(p^{m}).
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 p-th power. In certain contexts it is an automorphism, but this is not true in general.
In mathematics, the fundamental theorem of Galois theory is a result that describes the structure of certain types of field extensions in relation to groups. It was proved by Évariste Galois in his development of Galois theory.
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 domain. Polynomial factorization is one of the fundamental components of computer algebra systems.
In field theory, a simple extension is a field extension which is generated by the adjunction of a single element. Simple extensions are well understood and can be completely classified.
In field theory, a branch of mathematics, the minimal polynomial of a value α is, roughly speaking, the polynomial of lowest degree having coefficients of a specified type, such that α is a root of the polynomial. If the minimal polynomial of α exists, it is unique. The coefficient of the highest-degree term in the polynomial is required to be 1, and the specified type for the remaining coefficients could be integers, rational numbers, real numbers, or others.
In mathematics, a CM-field is a particular type of number field, so named for a close connection to the theory of complex multiplication. Another name used is J-field.