Prerequisites: basic concepts of abstract algebra, group theory, and ring theory
Introduction
Field theory is the theory of fields.
This article mainly concerns the theory of field extensions. A field is an algebraic structure closed under addition, subtraction, multiplication, and division. In algorithm competitions, taking a modulus by a prime is equivalent to performing computations in the finite field . As with the real field , some problems are more conveniently solved in a larger field, namely the complex field ; a common example is using the fast Fourier transform to accelerate multiplication of polynomials with real coefficients. Similar operations can be performed over finite fields. Most readers are relatively unfamiliar with extensions of finite fields, so understanding the general theory of field extensions is useful. At the end of the article, we give several algorithmic applications that require extending finite fields, and briefly discuss extensions of integer rings that may be needed in some applications.
Closely related to field theory is Galois theory. It connects field extensions with their automorphism groups, making it possible to understand the properties of field extensions using tools from group theory. Although this theory is often a core part of algebra courses, it is far removed from the content of algorithm competitions, so this article will not introduce it in much detail. Interested readers should consult relevant specialized books.
Notation
When there is no ambiguity, this article may omit multiplication symbols in rings and fields, write the ring as the ring , and write the field as the field . The additive identity of a ring or field is called the zero element, and the multiplicative identity is called the unity. In this article, is always a prime, while is always a prime power and can be written as , where is a positive integer.
Field extensions
As in the cases of groups and rings, we can define subfields and field homomorphisms.
Subfield
For a field , if its subring is also a field, then is called a subfield of .
Regardless of how the definitions of rings and subrings treat the unity, a subfield necessarily contains the unity of the field 1.
Field homomorphism
A ring homomorphism from a field to a field , , is also called a field homomorphism from to .
Unity under field homomorphisms
If, unlike the definition used in this article, ring homomorphisms are required to map the unity to the unity, then field homomorphisms naturally have the same requirement. Otherwise, the unity may also map to the zero element.
Since fields have only trivial ideals, a field homomorphism either maps the entire field to the zero element or is necessarily an embedding. Thus, discussing field homomorphisms can be reduced to discussing subfields.
For fields, the smaller field is often the more familiar one, so we usually take a subfield as the base point when studying a larger field. This is the concept of a field extension.
Field extension
For a field , if is a subfield of , then is called an extension (or an extension field) of , denoted by .
Notation for field extensions
Although the notation is formally the same, the concept of a field extension has nothing to do with quotient rings and should not be confused with them.
Example
The complex field is an extension of the real field , and the real field is an extension of the rational field .
Degree of a field extension
For a field extension , is always a vector space over . The dimension of this vector space is the degree of the field extension.
Degree of a field extension
The degree of a field extension is the dimension of viewed as a vector space over , namely , denoted by . If the degree of a field extension is finite, it is called a finite extension; otherwise it is called an infinite extension.
Example
The degree of the extension , , is , so it is a finite extension. The extension is infinite.
The degree of field extensions satisfies the multiplicative law.
Theorem
Let be fields; their extension degrees satisfy .
Proof
In the case of infinite extension degrees, this is obvious. Otherwise, if is a basis of as a vector space over , and is a basis of as a vector space over , then one can verify that is a basis of as a vector space over .
This article mainly discusses finite field extensions.
Characteristic of a field
A natural starting point for studying field extensions is the smallest subfield containing the unity of , which is also called the prime subfield of .
The structure of the prime subfield is uniquely determined by the properties of the field's unity. The characteristic of a field summarizes these properties.
Characteristic of a field
The characteristic of a field is the smallest positive integer for which holds, namely ; if no such exists, the characteristic of the field is . Here, means adding copies of the unity . If the characteristic of is not , then is said to have finite characteristic.
The characteristic of a field can be understood through ring homomorphisms. The integer ring is the structure closed under repeated addition, subtraction, and multiplication starting from and . It can be viewed as a kind of “prototype”: every ring containing a unity should “inherit” part of the structure of the integer ring2. Thus, for a field , consider the ring homomorphism satisfying . This ring homomorphism is uniquely determined: it maps to , the sum of copies of the unity . Its image embeds into the field , necessarily contains the unity, is commutative, and has no zero divisors, so it is an integral domain. Therefore, the kernel of the homomorphism is necessarily a prime ideal. The prime ideals of the integer ring can only have the form , where or is prime. This is the characteristic of the field.
The characteristic of a field determines the structure of its prime subfield:
- When the characteristic is , the homomorphism is injective, so the integer ring embeds into the field . The rational field , as the smallest field containing the integer ring, can also be embedded into ; it is the prime subfield of ;
- When the characteristic is a prime , the image of the homomorphism , , embeds into the field . In this case, is already a field, denoted by , and it is the prime subfield of .
These observations in fact establish the following conclusion:
Theorem
The characteristic of a field can only be or a prime . A field of characteristic has prime subfield , while a field of characteristic has prime subfield .
The and in the theorem are also called prime fields, that is, fields whose only subfield is themselves. A finite field necessarily has finite characteristic, because a field of characteristic contains at least the subfield .
Fields of finite characteristic and fields of characteristic zero often have different properties. For example, a field of finite characteristic has the following properties:
Theorem
Let have characteristic . Then:
- Every nonzero element of the additive group of has order , that is, for every , ;
- the “freshman's dream”: for every , . Consequently, the map is an injective endomorphism of , called the Frobenius endomorphism.
Proof
For the first property, it is enough to note that . For the second property, in the binomial expansion of , all the coefficients other than those of and are multiples of , so the first property gives . To verify that is an endomorphism, it remains only to verify , which follows because multiplication in a field is commutative. Finally, a ring homomorphism between fields that maps the unity to the unity is necessarily injective.
For a finite field, the Frobenius endomorphism is of course also surjective, and is therefore an automorphism of the field.
Simple extensions
As in the extension of the real field to the complex field, many extensions can be constructed by adjoining extra elements to a field and specifying their arithmetic properties. In general, to avoid the trouble caused by specifying these properties, consider a field extension and adjoin elements of to ; the rules for operating on these extra elements and elements of have already been determined in the larger field .
Extension generated by a subset
Let be a field extension and ; the extension generated by over (extension generated by over ) is the smallest subfield containing both and in , denoted by .
The simplest case is naturally the one in which the set contains only a few elements.
Finitely generated extension
Let be a field extension; if there is a finite set such that , then is a finitely generated extension of , also written .
Simple extension
Let be a field extension; if there is an such that , then is a simple extension of . The element is called the primitive element of this simple extension.
Examples
All of these examples are obtained by adjoining elements to from .
- For a square-free integer , the quadratic field is the simple extension obtained by adjoining it to , with . Its degree is , because is a basis.
- The field is obtained from by adjoining and . Of course , meaning that the final extension is independent of the order and manner in which the elements are adjoined. This is also a simple extension, because . Its degree is , because is a basis.
- The field is also a simple extension, where is the circle constant. It is an infinite extension, because already has a basis .
- The field is a finitely generated extension, but not a simple extension. Here, is the circle constant and is the base of the natural logarithm.
These examples show that simple extensions can have very different properties. This depends on the nature of the elements being adjoined.
Algebraic extensions
To analyze all possible situations that can arise when elements are adjoined to a field, let us imitate the earlier discussion of the characteristic of a field and consider ring homomorphisms from the polynomial ring to an extension . Here, plays the role of the integer ring : it is the “prototype” of the structure obtained in the field by adjoining the indeterminate and closing under addition, subtraction, and multiplication3.
Let a ring homomorphism satisfy that restricts to the identity on and , that is, let it map the indeterminate to an element of the extension . Since its image is necessarily an integral domain, the kernel is necessarily a prime ideal of the polynomial ring . A polynomial ring over a field is a principal ideal domain, so the kernel necessarily has the form , where or is an irreducible element of . There are two cases:
-
When the kernel of the homomorphism is , the polynomial ring embeds into , and its image is an integral domain. Therefore, the smallest field in containing both and is the field of fractions of , namely . This notation can be interpreted either as taking the indeterminate in the rational function field and substituting it with , or as the simple extension generated over by ; these two interpretations give the same result in this context;
-
When the kernel of the homomorphism is and is irreducible, we have , that is, is a root over of the polynomial . Since is a field, we may assume that is monic. The image of the homomorphism is then the field , so
This case can be further divided into two cases:
- If is a linear polynomial, that is, , then , so the extension is trivial;
- In all other cases, is an irreducible polynomial of degree greater than one, and ; the image is already a field containing and , so it is , the extension generated over by , and is nontrivial.
These observations motivate the following definitions:
Algebraic and transcendental elements
For an extension , if an element is a root over of a nonzero polynomial , then is algebraic over ; otherwise, is transcendental over .
Minimal polynomial
For an element algebraic over a field , namely , the monic polynomial having as a root and having smallest degree, , is called its minimal polynomial.
This minimal polynomial is the irreducible polynomial in the analysis above. Of course, one can also prove directly that minimal polynomials are irreducible. The minimality of the minimal polynomial means that whenever a polynomial over has as a root, it must have as a factor.
Examples
- is algebraic over , and its minimal polynomial is .
- is algebraic over , and its minimal polynomial is .
- is transcendental over .
- In general, an element algebraic over is called an algebraic number, while a transcendental element is called a transcendental number. In particular, if the minimal polynomial of an algebraic number is monic, it is called an algebraic integer. All algebraic integers in an algebraic extension form a ring. For example, the algebraic integers in the quadratic field form the quadratic integer ring . The meaning of this notation is given on the quadratic integer ring page.
Algebraic and transcendental extensions
For an extension , if every element of the field is algebraic over , then is an algebraic extension of ; otherwise, is a transcendental extension of .
Depending on the nature of the adjoined element, the result of a simple extension can be divided into two types. When the adjoined element is transcendental, the simple extension is always isomorphic to a rational function field. In this case, there is no possibility of further simplification. However, when the adjoined element is algebraic, the simple extension is actually , namely the result obtained by directly using to replace the indeterminate in the polynomial ring , namely . From an elementary point of view, compared with the transcendental case, elements in the extension field can have no denominator; this means that a process analogous to “rationalizing the denominator” in elementary arithmetic is always possible in a simple algebraic extension. Since the extensions involved in algorithm competitions are mainly simple algebraic extensions, the next section discusses their computation in greater detail.
The importance of simple algebraic extensions is also reflected in the following theorem:
Theorem
A field extension is finite if and only if it is a finitely generated algebraic extension.
Proof
Let be a field, and let be a finitely generated algebraic extension of a field, that is, every is algebraic over . Let , so and . Notice that is necessarily algebraic over , because the minimal polynomial of over the field is also a polynomial over ; moreover, the degree of the minimal polynomial of over cannot exceed the degree of the minimal polynomial of over the field . Therefore, is necessarily finite, and by the multiplicative law for field extension degrees, is also finite. Conversely, starting from , for each that has already been constructed, choose an element in , namely , and adjoin it to to obtain the extension , until . Since the degree of the extension keeps decreasing, this process must terminate after finitely many steps. Therefore, every finite extension is a finitely generated algebraic extension.
This means that to understand the properties of finite extensions, it is enough to understand simple algebraic extensions. A finite extension can always be obtained through finitely many simple algebraic extensions.
Structure and computation of simple algebraic extensions
In this section, let be a number field, let be an extension of it, and let be algebraic over . Let the minimal polynomial of be , and let be a monic polynomial of degree , namely
where and is irreducible over .
The isomorphism shows that operations in the extension field are computations with polynomials modulo . By polynomial division with remainder, it is enough to consider the congruence classes of all polynomials of degree less than . A natural basis for these polynomials is . Therefore, we have the following conclusion:
Theorem
Under the assumptions of this section, the extension field can be written as
Here, ranges over all polynomials of degree less than . Therefore, the extension degree , namely, the degree of the minimal polynomial of . In the extension field, addition of and is polynomial addition, that is, the coefficients at corresponding positions are added; multiplication of and has a result that can be written as , where is the remainder when the product is divided by .
As a field, one can of course also calculate division of elements in . According to the multiplication process described in the theorem, this amounts to solving a linear congruence equation over a polynomial ring. By analogy with the method for integers, to calculate the quotient , one can first determine the multiplicative inverse of and then multiply it by . To calculate the multiplicative inverse of , it is enough to solve the congruence . This can be done using the extended Euclidean algorithm.
The details of the computation are illustrated below with several concrete examples.
Example
Consider the extension field , where is a root of the equation . We want to calculate
its value.
The first step is to calculate the inverse of , that is, to solve the congruence equation
Apply the extended Euclidean algorithm. First perform the Euclidean division, obtaining:
Next compute the coefficients in the congruence equation:
Therefore, the solution to the equation is
This shows that the inverse of is
The second step is to calculate the product of the inverse and . We have
This is the final answer.
In the example, we only used the condition that is a root of the equation, without specifying which particular root it is. The polynomial has one real root and a pair of conjugate complex roots in the complex field ; adjoining any one of these roots to the rational field gives an extension isomorphic to the others. In other words, from the algebraic point of view, these three distinct roots are indistinguishable.
In general, for a field and an irreducible polynomial over it, if it has distinct roots in an extension field, these roots have the same algebraic properties when they are separately used to form simple extensions of ; the roots are called conjugates of one another. The usual notion of conjugation in the complex field is a special case of this concept for the field extension .
Example
Consider the extension field , where is a root of the equation . In general, the operations on and are
This provides arithmetic rules analogous to those in the complex field. Most readers will be unfamiliar with such a root , but this does not prevent us from performing operations on elements of this field. In fact, , so as a vector space ; that is, the result is a finite field of size . We will see later that all finite fields are constructed in this way.
For small computations, reducing modulo a monic polynomial can usually be done by substituting
to lower the degree of the target polynomial. Moreover, for low-degree extensions, one can often directly derive the coefficient operation rules and use an implementation similar to a complex-number class, without carrying out a modular reduction every time.
As an example of a simple algebraic extension, see the reference implementation of finite fields below.
The algorithms described here can in practice handle only relatively low extension degrees, which is sufficient for most applications in algorithm competitions. When the extension degree is high enough to become a complexity bottleneck, appropriate polynomial techniques (fast Fourier transform, number-theoretic transform, fast polynomial remainder computation, polynomial Euclidean algorithm, and so on) should be used to accelerate the computations.
Splitting fields
The structure of simple algebraic extensions was discussed in detail above. However, such an extension is often not sufficient:
Example
Consider the extension . The algebraic element in the field has minimal polynomial . In the complex field , the polynomial has three roots, namely , where is a primitive third root of . Although , the other two roots are not in , so an operation such as cannot even be performed there. To fully study these three roots, we need to extend further, namely to .
As explained above, such an extension can be made by successively forming simple extensions of the elements. It should be noted that the minimal polynomial of over is different from its minimal polynomial over : the former is , while the latter is , because
After the original minimal polynomial factors into linear factors when the field is extended, the degree of the minimal polynomial of the remaining roots is lower than its degree over the original field. The process of continually extending the field is a process of continually “splitting” the polynomial. Therefore, every time a simple extension is formed, the minimal polynomial must be determined again.
Adjoining all the roots of a polynomial to a field gives its splitting field.
Splitting
Let be a field. If a polynomial can be factored in as a product of linear factors, then is said to split over .
Splitting field
For a field and a polynomial over it, if an extension makes split in but it does not split in any proper subfield of , then is the splitting field of .
As with simple extensions, one can prove that the splitting field of a given polynomial is unique up to isomorphism, independently of the construction method. A splitting field is always a finite extension.
Normal extension
For an algebraic extension , if, for every , the minimal polynomial of splits in , then is a normal extension of .
Normal extensions play a foundational role in Galois theory.
Algebraically closed fields
Most of the extension concepts mentioned above are, in principle, defined inside a field larger than the extension. For simple extensions, polynomial rings allow us to construct a field extension without relying on a larger field, but there is no such method in general. For the rational field and the real field , we can always assume that algebraic extensions are contained in the complex field . For finite fields, there is no analogous known field. In fact, every field has an algebraic closure, so all algebraic extensions of a field can be assumed to be formed inside its algebraic closure. This completely resolves the issue.
Algebraic closure
For a field , if a field is an algebraic extension of and every splits in , then is an algebraic closure of .
An algebraic closure is a normal extension of the field. Its construction is essentially the process of adjoining the roots of all possible polynomials to the field. As with a splitting field, the algebraic closure of a field is also unique up to isomorphism.
Theorem
Every field has an algebraic closure.
Proof
The difficulty of the proof comes from set theory. Here we quote a proof by Artin.
The first part starts from and constructs an extension such that every polynomial over has at least one root in . For the field , consider the multivariable polynomial ring4 , where the subscript of the indeterminate ranges over all monic polynomials over . Let all generate an ideal . First, , so a maximal ideal exists. Otherwise, if , there must be finitely many monic polynomials over a field , denoted , and corresponding elements in the ring , denoted such that . Let be the algebraic extension obtained by adjoining to roots of the polynomials , denoted by ; in , substitute every in the identity above with , and in each substitute for the other indeterminates the value , and in this gives the equality , a contradiction. Thus , and the construction of the maximal ideal is valid. The quotient ring is a field, denoted by , and every monic polynomial over , , has a root in , namely .
The second part inductively constructs an algebraically closed field containing , denoted by (the definition is given below). Repeating the construction above, from a field we can construct a field in which every polynomial over has at least one root in . Moreover, embeds naturally into , so we can define their union . It is easy to verify that this is also a field, and the coefficients of every polynomial over must all be contained in some , so one of its roots must appear in . This shows that every polynomial over has at least one root in , so is an algebraically closed field.
Finally, let the set of all elements of that are algebraic over be denoted by . It is clearly a field, because for any , we have . It is also an algebraic extension of , because all its elements are algebraic over . For a polynomial over , namely , all its roots are algebraic over , so they also lie in and therefore it must split into a product of linear factors. This proves that is an algebraic closure of .
Examples
- The algebraic closure of the real field is the complex field .
- The algebraic closure of the rational field is the set of all algebraic numbers (that is, the set of algebraic elements in the field extension ), denoted by .
Every algebraic extension of an algebraic closure is trivial. Such a field is called an algebraically closed field.
Algebraically closed field
If a field has every nonconstant polynomial with at least one root , then is called an algebraically closed field.
In fact, it has the following equivalent definitions:
Theorem
For a field , the following properties are equivalent:
- The field is algebraically closed;
- every polynomial over , namely , splits;
- the only irreducible polynomials over are linear polynomials;
- has no nontrivial algebraic extensions;
- has no nontrivial finite extensions;
- is the algebraic closure of some field.
Proof
The equivalence of the first five properties is obvious from the definitions. For the sixth, an algebraically closed field is clearly its own algebraic closure, because it has no nontrivial algebraic extensions. Conversely, we prove that the algebraic closure of a field is necessarily algebraically closed. Let be the algebraic closure of , and let be a polynomial over . Let be a root of in the splitting field of , and let the set of nonzero coefficients of be . Since is a finite extension, must also be algebraic over ; therefore, by the definition of an algebraic closure, the minimal polynomial of over splits in the field , so . This shows that every polynomial over has at least one root.
Finally, the fundamental theorem of algebra 5 shows that is algebraically closed. An irreducible polynomial over the real field has degree at most two, or equivalently, its algebraic extensions have degree at most two, because the largest field obtainable through algebraic extensions is .
Separable extensions
The concept of a splitting field guarantees that for any polynomial over any field, there is always an extension that contains all its roots, and the splitting field precisely gives the smallest such extension. The properties of a polynomial are closely related to the properties of its splitting field. However, if we want to study the properties of a polynomial through its splitting field, we first face the problem that the splitting field is independent of the multiplicities of the roots of the polynomial. Therefore, whenever possible, we should consider a kind of “simplest representation” of the polynomial. Motivated by this, a polynomial that has no repeated roots even in the algebraic closure of the field is called a separable polynomial.
Separable polynomial
For a field , if a polynomial has no repeated roots, that is, if has no repeated factors in the algebraic closure of the field , , then its factorization into linear factors has no repeated factors, and is called separable.
Because we always extend to the algebraic closure of when discussing this, whether a polynomial is separable is actually independent of the choice of the field . However, because the coefficients of the polynomial lie in , we should give a test that can determine whether a polynomial is separable over without explicitly constructing its extension.
Readers familiar with analysis know that whether a polynomial function has repeated roots can be determined using its derivative: a repeated root of a polynomial function is also a root of its derivative. Although polynomials and polynomial functions are not identical concepts, the method for determining whether a polynomial function has repeated roots can be transferred to polynomials by analogy. The derivative of a polynomial can be defined formally as follows:
Formal derivative
For the polynomial over a field
its (formal) derivative (derivative), denoted by , is defined as the polynomial
This definition applies to polynomials over every field and does not depend on any topological structure; here the derivative operator merely maps one polynomial to another. Moreover, by comparing coefficients, one can verify that familiar differentiation rules, such as , still hold for formal derivatives.
Consequently, to check whether the polynomial and its derivative have a common root in the splitting field, we need not explicitly construct this splitting field, but can determine it through their greatest common divisor; this is because the roots of a polynomial always occur in its minimal polynomial, and a repeated root means that the corresponding minimal-polynomial factor is also repeated. Thus, the criterion for repeated roots is as follows:
Theorem
For a field , for a polynomial , if has a repeated root , then its derivative also has the same root . Consequently, a necessary and sufficient condition for the polynomial to be separable is that and its derivative are coprime, namely, .
Proof
First, because division with remainder remains valid in an extension, the result of the Euclidean algorithm is also independent of the choice of extension, so it is enough to discuss their common factors in the splitting field. Let be a root of of multiplicity ; then in the splitting field we have the factorization , so its derivative necessarily also has the root . Conversely, if both and have the root , then for the factorization in the splitting field, we have , so is also a root of and hence is a repeated root of . This proves the first part of the theorem. Furthermore, has a repeated root if and only if is a factor of . Therefore, is inseparable if and only if the degree of is at least one.
A polynomial over a field can always be factored as a product of irreducible polynomials. Since distinct irreducible polynomials (up to associates) always have distinct roots, repeated roots are naturally related to repeated polynomial factors. Then, if the factorization of a polynomial has no repeated irreducible factors, can we determine that the polynomial is separable? In other words, are all irreducible polynomials separable? Unfortunately, in general the answer cannot be affirmative. The problem occurs over fields of finite characteristic.
For a field , let be an irreducible polynomial; the polynomial , as a factor of , can only have two possibilities, namely or . In the former case, the polynomial is naturally separable; the problem occurs in the latter case. However, because the definition of the derivative already guarantees that or , the fact that is a factor of can only mean that . This is possible over fields of finite characteristic.
For a field of characteristic , denoted , if , then all nonzero coefficients of the polynomial can occur only in terms whose degrees are exactly multiples of , that is, the polynomial can be written as
If a field has a polynomial that is both irreducible and inseparable, it can only have this form. However, if every element of the field has a -th root, that is, for every coefficient there is a such that can be written in the form , then, by the Frobenius endomorphism, we have
Therefore, no irreducible polynomial of this form exists over such a field . Consequently, all irreducible polynomials over such a field are separable. Such a field is called a perfect field.
Perfect field
If all irreducible polynomials over the field are separable polynomials, then the field is called a perfect field.
For a perfect field, the concept of a separable polynomial is equivalent to the concept of a polynomial without a square factor in its unique factorization.
Theorem
Let be a perfect field; then a polynomial over is separable if and only if it can be written as a product of several distinct irreducible polynomials (up to associates).
The discussion in this section is actually enough to provide a method for removing repeated factors from a polynomial; it is a key step in polynomial factorization algorithms. But this is beyond the scope of this article, and interested readers can consult the relevant references at the end.
These observations also give a characterization of perfect fields:
Theorem
A field is perfect if and only if the characteristic of is zero, or the characteristic of is and every element has a -th root (that is, the Frobenius endomorphism is also an automorphism).
The rational field and the finite field discussed below are both perfect fields.
When the field is not perfect, inseparable irreducible polynomials do indeed exist.
Example
Consider , its rational function field , and the polynomial over that field. Since is the field of fractions of the unique factorization domain , and is a prime element of , applying Eisenstein's criterion to the prime element shows that is irreducible in , and hence also irreducible in . However, its derivative is , so is not separable. In fact, in the extension , it has the double root .
We now return to the discussion of field extensions.
Separable extension
For an algebraic extension , if, for every , the minimal polynomial of is a separable polynomial, then is called a separable extension of .
Algebraic extensions over perfect fields are all separable extensions. This can also serve as an equivalent definition of a perfect field.
If an algebraic extension is both a normal extension and a separable extension, it is also called a Galois extension. In a Galois extension, every irreducible polynomial has no repeated roots, and the number of roots is exactly equal to the degree of the polynomial, so permutations of the roots can fully reflect the properties of the field extension and the polynomial. Such extensions provide the foundation for establishing Galois theory. Interested readers can consult the relevant references at the end.
Cyclotomic fields
As a simple example of field extensions, this section discusses cyclotomic fields. Another simple example of a field extension is a quadratic field.
Group of roots of unity
In the complex field , the roots of the polynomial are called -th roots of unity (-th root of unity). Let . Then all -th roots of unity form the set . Under multiplication, forms a cyclic group of order , which can be written as and is called the group of -th roots of unity. The generators of the group , that is, those elements whose order is exactly , are called primitive -th roots of unity (primitive -th root of unity). The set of primitive -th roots of unity is , and it has exactly elements, where is the Euler totient function. Classifying the elements of the group of roots of unity by their orders gives the following decomposition:
Counting the elements on both sides gives the identity .
Cyclotomic fields
A cyclotomic field is an extension obtained by adjoining roots of unity to the rational field.
Cyclotomic field
The extension obtained by adjoining the complex -th root of unity to the rational field , namely , is called the -th cyclotomic field (-th cyclotomic field).
Because all -th roots of unity form the cyclic group under multiplication, the cyclotomic field also contains all these -th roots of unity. In fact, is precisely the splitting field over of the polynomial .
Theorem
The cyclotomic field is the splitting field over the rational field of the polynomial .
Proof
Let be the splitting field over the rational field of the polynomial . Since contains all complex roots of the polynomial , we have . Conversely, since , we necessarily have . This shows that .
This can serve as an equivalent definition of a cyclotomic field. In fact, adjoining any primitive -th root of unity to the field gives .
Cyclotomic polynomials
The cyclotomic field is a simple algebraic extension of the rational field . According to the preceding analysis, such a field is always isomorphic to a quotient ring of some polynomial ring. To obtain this isomorphism, we need to analyze 's minimal polynomial . Since is a root of , must be a factor of . This means that we need to consider the factorization of in . By Gauss's lemma, it can necessarily be factored in as a product of monic irreducible polynomials.
Since is a splitting field, the polynomial has the factorization:
Since roots of unity of different orders have different algebraic properties, they cannot be roots of the same irreducible polynomial. Therefore, to study the minimal polynomial of , it is enough to consider the factor in the above factorization
The minimal polynomial of the root of unity must be a factor of . Moreover, the defined in this way has the following property:
Theorem
is a monic polynomial with integer coefficients and is irreducible in .
Proof
By definition, is clearly monic. First, we prove that . By Gauss's lemma, the polynomial has the same factorization in and , and every factor is a monic polynomial with integer coefficients. In this factorization, every factor is irreducible over and splits in ; all its roots are -th roots of unity and necessarily have the same order, so these roots must all belong to a single rather than being distributed among different . This means that every factor is a factor of some . Therefore, can be written as a product of monic polynomials with integer coefficients, and is necessarily itself a monic polynomial with integer coefficients.
Next, we prove that is irreducible in . Suppose it factors as , with irreducible in ; it is therefore enough to prove that contains all -th primitive roots of unity. In other words, let be a root of ; we need to prove that for every , is also a root of ; since can always be decomposed as a product of primes, it suffices to prove that for every prime , is a root of . Suppose otherwise that is a root of . Thus, is a common root in of the polynomials and . Since is the minimal polynomial of over , must divide ; equivalently, there exists such that . Reducing both sides modulo gives over the equation . By the Frobenius endomorphism, . Since is also a unique factorization domain, and must have a nontrivial common factor; therefore, is inseparable over . However, since , its formal derivative is coprime to it, contradicting its inseparability. Hence must indeed be a root of , and therefore contains all -th primitive roots of unity; it is .
This shows that it is the minimal polynomial of , also called the -th cyclotomic polynomial (-th cyclotomic polynomial). The definition above shows that it has complex roots, and these complex roots are exactly all -th primitive roots of unity; here, is the Euler totient function. This also shows that is an extension of degree .
The ring of algebraic integers in the cyclotomic field is . In addition, when , the cyclotomic field is a quadratic extension. Specifically, is the quadratic field ; and are the same, and both are the quadratic field .
Using cyclotomic polynomials, the polynomial has the unique factorization in
Therefore, if and only if . Moreover, applying Möbius inversion to this formula yields
Using this expression, all cyclotomic polynomials can be computed recursively. Here are examples of the first few cyclotomic polynomials, so that readers can become familiar with them.
Cyclotomic polynomials
The first cyclotomic polynomials are as follows:
An interesting fact is that, although these cyclotomic polynomials appear to have coefficients only and , this is not true for general . The first counterexample occurs at , and it can be proved that as grows, its coefficients can attain arbitrarily large values.
Using the Möbius inversion formula above, we can summarize the following properties to simplify computation of :
Properties
For the cyclotomic polynomial , we have:
- If for a prime p, then ;
- If for a prime p, then ;
- In particular, if is odd, then ;
- For a prime , we have ;
- In particular, .
These properties show that, when computing cyclotomic polynomials, the key cases are those in which the degree is an odd square-free number. For such cases, prime factors can be added one at a time using Property 2; adding each prime factor requires only one polynomial division.
Cyclotomic polynomials have many other properties.
Theorem
Let be the n-th cyclotomic polynomial for , whose degree is . Then:
- is a palindromic polynomial; its coefficient of degree equals that of degree , that is, ;
- The coefficient of degree of the polynomial equals the Möbius function ;
- If is a prime power , then ; otherwise, ;
- Let , and let be a prime factor of ; then , or is the order in the multiplicative group of , and these two cases cannot occur simultaneously.
Proof
The first three properties follow just by using Möbius inversion. For 1, directly consider the Möbius inversion form of , namely ; for 2, let the coefficient of of degree be ; comparing on both sides of the coefficients of degree gives , and we then apply Möbius inversion; for 3, divide both sides of by , then substitute , obtaining , and apply Möbius inversion.
We now prove the fourth property. First, if is the order in the multiplicative group of , then is the smallest positive integer satisfying , and hence . Conversely, if , then ; but if is not the order in the multiplicative group of , let its order be ; then necessarily and . Thus, and have the common root in the field of , which means that has the multiple root . This implies ; otherwise, is coprime to its derivative and hence separable over , so it cannot have a multiple root. Therefore, has a prime factor , and it falls into only two cases: , or is the order in the multiplicative group of . These cases are mutually exclusive, because the latter implies .
Cyclotomic polynomials can also be used to solve certain problems in number theory and algebra. For example, the length of the repetend when a fraction is written as a decimal in a given base is closely related to cyclotomic polynomials. Readers interested in these specific applications may consult the references at the end.
Finite fields
Finite field (finite field), also called a Galois field (Galois field), is a field with only finitely many elements. The structure of a finite field is uniquely determined by the number of its elements, and that number must be a power of a prime.
Theorem
A field of size exists if and only if has the form of a prime power . Moreover, such a field is unique up to isomorphism and is denoted by . The prime is the characteristic of the field , and the positive integer is the degree of the field extension . Finally, is the splitting field over of the polynomial , and contains exactly the distinct roots of , namely the roots$.
Proof
Let be a finite field. The characteristic of is necessarily finite; denote it by ; thus, has the prime subfield . Moreover, must be a finite extension of ; denote its degree by . As a vector space over of dimension , the field has elements. The nonzero elements of form the group , whose order is , so . Therefore, every element of satisfies ; that is, they are the distinct roots of the polynomial , namely the roots. Thus, in , the polynomial has the factor ; but this factor already has degree and leading coefficient , so . This shows that splits over . Any field over which splits, since has distinct roots, must have at least elements. Thus, is the smallest field over which splits, that is, the splitting field of . In summary, a finite field of size must be the splitting field over its prime subfield of the polynomial . Since splitting fields are unique up to isomorphism, a field of size is unique as well.
Conversely, given a prime and its power , it suffices to show that the splitting field over of the polynomial has exactly elements to establish the existence of all fields of prime-power order . Since the splitting field over of the polynomial always exists, let the set of all roots of the polynomial in that splitting field be . We now prove that is a field, and hence is the splitting field of itself. Iterating the Frobenius endomorphism times shows that is also an endomorphism; therefore, for any , we have , , and . Hence, is closed under addition, subtraction, multiplication, and division, so it is a field. This shows that is the splitting field over of the polynomial .
Corollary
In the finite field (), the sum of all nonzero elements is , and their product is .
Proof
The nonzero elements of a finite field are exactly the roots of the polynomial , namely the roots$; the result follows from Vieta's formulas.
In the prime field , the conclusion about the product in this corollary is precisely (part of) the Wilson theorem in number theory.
Multiplicative structure
The multiplicative group of a finite field is always a cyclic group.
Theorem
Every finite subgroup of the multiplicative group of a field is cyclic.
Proof
Let be a subgroup of the multiplicative group of a field , with . Thus, is a finite Abelian group. By the fundamental theorem of finite Abelian groups, has the invariant factor decomposition with . Therefore, every element of , say , satisfies . In other words, the elements of are roots over the field of the polynomial . However, the polynomial has at most distinct roots, so . On the other hand, , and hence . This shows that , that is, is cyclic.
Corollary
The multiplicative group of a finite field satisfies .
The cyclic group has generators, called primitive elements of the finite field; here, is the Euler totient function.
Primitive element
A generator of the multiplicative group of a finite field is called a primitive element of (primitive element).
Primitive elements in simple extensions and finite fields are different
Although primitive elements in simple extensions and primitive elements in finite fields have the same name, they are not the same. A primitive element in a simple extension is a generator of the corresponding simple extension, whereas a primitive element in a finite field is a generator of the corresponding multiplicative group (viewed as a cyclic group). A primitive element of a finite field considered as a simple extension of its prime subfield need not be a primitive element of the finite field itself. For example, in , is a primitive element of the field extension, but it is not a primitive element of the field , because its order is .
Primitive elements in and primitive roots modulo are also different
For a finite field of odd characteristic, there always exists a primitive root modulo . However, it should not be confused with a primitive element in the finite field . Although both are generators of their respective multiplicative structures when viewed as cyclic groups, and are not the same when itself is not prime. For example, the order of the former is , while that of the latter is , so the two multiplicative groups do not have the same size.
Let be a primitive element of the finite field . Then, for every , there is a unique natural number such that ; this is called the discrete logarithm over of the element with respect to the base . As in the case of , the complexity of discrete logarithm algorithms is relatively high.
Through multiplication, a primitive element can already generate all nonzero elements of the field. This shows that a finite field is necessarily a simple extension of each of its subfields.
Theorem
For a finite field , let be a subfield of ; then is a simple algebraic extension of ; moreover, if is a primitive element of , then .
The minimal polynomial of a primitive element is an irreducible polynomial over a subfield of the finite field.
Inclusion relations
The subfields of a finite field are also finite fields. The inclusion relations among finite fields are completely determined by their orders.
Theorem
Let and be finite fields; then is a subfield of if and only if there exists such that . In other words, is a subfield of if and only if .
Proof
If is a subfield of , then they necessarily have the same characteristic . The field extensions , , and are all simple algebraic extensions; denote their degrees by , respectively; then the degrees necessarily satisfy . Moreover, and , and .
Conversely, we prove that for every , is a subfield of . Let and . Let be the set of all roots in the finite field of the equation . The Frobenius endomorphism shows that is a field; the key is to prove that there are exactly such roots, which gives . Since , we have , so , that is, . Hence, splits over , and therefore has distinct roots in , namely roots. This shows that is a subfield of .
This theorem shows that the inclusion relations among finite fields correspond to the divisibility relations among the exponents in their orders , namely . The lattice formed by all finite fields of characteristic , namely , is therefore isomorphic to the lattice formed by the integers under divisibility. Of course, for intersections and similar operations among finite fields to make sense, all fields of characteristic must be embedded into an algebraic closure of .
Theorem
Let be an algebraic closure of ; then the set of roots in of the polynomial forms the finite field . Then:
- , that is, the algebraic closure of is the union of all finite fields of characteristic ;
- The lattice formed by all finite fields of characteristic , namely , under inclusion is isomorphic to the lattice formed by the integers under divisibility. In particular, the intersection of and is , while the smallest field containing both and is .
Proof
The key is to prove the first part, namely that is an algebraic closure of . The second part is a simple consequence of the preceding theorem about subfields of finite fields.
Note that for any , there necessarily exists such that ; hence is algebraic over ; therefore, is an algebraic extension of . For any polynomial over of degree , denoted , the algebraic closure contains at most distinct roots of it. Let the degree of the minimal polynomial of the root be ; then must lie in the field ; hence all roots of lie in the set , that is, splits over the set . By the definition of an algebraic closure, is the algebraic closure of .
Automorphism groups
The subfields of a finite field are all sets of roots of polynomials of the form . In other words, they are fixed-point sets of some map . This in fact reveals a deep correspondence between subfields of finite fields and subgroups of their automorphism groups.
Every field of characteristic has the Frobenius endomorphism . For a finite field , this is also an automorphism; this shows that all finite fields are perfect fields. The automorphism group of the field is the cyclic group of order , written , and one of its generators is the Frobenius endomorphism .
Theorem
The automorphism group of a finite field , , is a cyclic group of order , and its generator is the Frobenius endomorphism .
Proof
First, the Frobenius endomorphism is an automorphism on the finite field , because an injective map on a finite set is necessarily surjective. Thus, .
Next, the order of is . This is because for every , , so is the identity map; moreover, for every , is not the identity map, since otherwise all elements of would be roots of , which is impossible.
Finally, has at most elements. Let be a primitive element of ; then an automorphism is uniquely determined by its value at , namely . However, must map to one of its conjugates; otherwise, and would no longer be roots of the same minimal polynomial. There are only such conjugates, which shows that also has at most elements.
Therefore, the elements of , numbering in total, are exactly . The theorem follows.
The subgroups of the automorphism group are in one-to-one correspondence with the subfields of the finite field .
Theorem
Let be a finite field, let be the set of all its subfields, and let be the set of all subgroups of its automorphism group . Then:
- For , let be the set of automorphisms in that leave invariant, namely ; then ;
- For , let be the intersection of the fixed-point sets of all automorphisms in , namely ; then is a subfield of ;
- The maps and are inverse to each other and give a one-to-one correspondence between and ;
- This one-to-one correspondence maps extension relations between subfields to inclusion relations between subgroups: for any , we have .
This conclusion is a special case of the fundamental theorem of Galois theory; it connects field extensions with group theory, allowing field-extension problems to be solved using group-theoretic methods.
Irreducible polynomials
Irreducible polynomials over a finite field are particularly easy to determine. Every irreducible polynomial over the finite field of degree corresponds to an algebraic extension of degree , and such an extension is unique; therefore, the roots of all degree- irreducible polynomials can be found in . This shows that every irreducible polynomial over of degree is a factor of . To determine all irreducible polynomials over of degree , we need to consider the factorization of over . This is very similar to the cyclotomic-polynomial case.
Algebraic elements over the rational-number field can be classified according to the degree of their minimal polynomials. Let be the set of algebraic elements whose minimal polynomial has degree exactly , then
This corresponds to the factorization
Since a degree- irreducible polynomial has roots, and the minimal polynomials of these roots all have degree , every degree- irreducible polynomial must be a factor of the polynomial
a factor; this expression is obtained by applying Möbius inversion to the preceding factorization. Since the degree of this polynomial is
Therefore, over , the total number of monic irreducible polynomials of degree is
.This is exactly the number of necklaces formed from colored beads with length , up to rotation (proof); hence it is also called the necklace polynomial (necklace polynomial).
Theorem
There exist irreducible polynomials of every degree over the finite field .
Because irreducible polynomials over finite fields have a simple structure, factoring polynomials over finite fields is quite easy. For example, to determine all degree- irreducible factors of a given polynomial, it suffices to find the greatest common divisor of the given polynomial and 6. Similarly, if a degree- polynomial is coprime, for every , to the polynomial , then it can be concluded that the degree- polynomial is irreducible over .
As noted above, the roots of an irreducible polynomial over a finite field need not be primitive elements of the corresponding extension field. A primitive element of the finite field has a minimal polynomial over its prime subfield , which is also called a primitive polynomial7 over the field (primitive polynomial). Using such a polynomial to construct an extension guarantees that is a primitive element of the extension. Primitive polynomials over the field of degree can be obtained by factoring over the cyclotomic polynomial .
Theorem
Let be a prime, let be a positive integer, and suppose . Let be the order in the multiplicative group of the element . Then, the cyclotomic polynomial over the field factors as the product of primitive polynomials of degree . In particular, the cyclotomic polynomial is irreducible over if and only if is a primitive root modulo .
Proof
If we note that the roots of the -th cyclotomic polynomial are all primitive roots of unity of of order , and that the minimal polynomial of an -th primitive root of unity has degree , which is the number of its conjugates (including itself) and also its orbit length under the automorphism group , then is the orbit length of the cyclic subgroup acting on by ; namely, in the multiplicative group , it is the order of . If one does not want to rely on Galois theory, this can also be proved by showing that is the smallest positive integer for which holds. The remaining conclusions are obvious.
Although irreducible polynomials are important for constructing finite fields, there is no particularly good deterministic method for finding, over a finite field , an irreducible polynomial of degree . In general, a random method can be used to generate such an irreducible polynomial. Since, among all monic polynomials of degree , irreducible polynomials account for a proportion , we can first generate a monic polynomial of degree at random and then test whether it is reducible. In this way, an irreducible polynomial can be found after generating an expected monic polynomials. Of course, an irreducible polynomial generated this way need not be primitive, and its coefficients need not be simple. In practice, if the size of the finite field is known in advance, one can often find a primitive polynomial with simple coefficients by consulting a table8, which facilitates subsequent computations.
Reference implementation
This section provides a naive implementation of a finite field for reference only. The code implements a method for randomly generating an irreducible polynomial.
Reference implementation
#include <iostream>
#include <random>
#include <vector>
class FiniteField {
int p, k;
std::vector<int> mod; // Monic.
// Remove leadings zeros of a polynomial.
static void trim(std::vector<int>& poly) {
int m = poly.size();
for (; m && !poly[m - 1]; --m);
poly.resize(m);
}
// Binary exponentiation mod p.
int pow(int a, int b) const {
int res = 1, po = a;
while (b) {
if (b & 1) res = (long long)res * po % p;
po = (long long)po * po % p;
b >>= 1;
}
return res;
}
// Multiplicative inverse mod p.
int inv(int a) const { return pow(a, p - 2); }
// Polynomial GCD. Inputs are supposed to have no leading zeros.
std::vector<int> poly_gcd(const std::vector<int>& lhs,
const std::vector<int>& rhs) const {
if (lhs.size() < rhs.size()) {
return poly_gcd(rhs, lhs);
} else if (rhs.size()) {
auto rem = lhs; // remainder.
long long v = inv(rhs.back());
for (int i = rem.size() - rhs.size(); i >= 0; --i) {
auto d = v * (p - rem[i + rhs.size() - 1]) % p;
for (int j = 0; j < rhs.size(); ++j) {
rem[i + j] = (rem[i + j] + d * rhs[j]) % p;
}
}
trim(rem); // Remove leading zeros.
return poly_gcd(rhs, rem);
} else {
return lhs;
}
}
// Polynomials Ex-GCD. Inputs are supposed to have no leading zeros.
void poly_ex_gcd(const std::vector<int>& lhs, const std::vector<int>& rhs,
std::vector<int>& x, std::vector<int>& y) const {
if (lhs.size() < rhs.size()) {
poly_ex_gcd(rhs, lhs, y, x);
} else if (rhs.size()) {
std::vector<int> quo(lhs.size() - rhs.size() + 1); // quotient.
auto rem = lhs; // remainder.
long long v = inv(rhs.back());
for (int i = rem.size() - rhs.size(); i >= 0; --i) {
quo[i] = v * rem[i + rhs.size() - 1] % p;
long long d = p - quo[i]; // d = -quo[i].
for (int j = 0; j < rhs.size(); ++j) {
rem[i + j] = (rem[i + j] + d * rhs[j]) % p;
}
}
trim(rem); // Remove leading zeros.
// Recursively ex_gcd.
poly_ex_gcd(rhs, rem, y, x);
// y -= a/b*x.
if (y.size() < quo.size() + x.size() - 1) {
y.resize(quo.size() + x.size() - 1, 0);
}
for (int i = 0; i < quo.size(); ++i) {
for (int j = 0; j < x.size(); ++j) {
y[i + j] = (y[i + j] - (long long)quo[i] * x[j]) % p;
if (y[i + j] < 0) y[i + j] += p;
}
}
trim(y); // Remove leading zeros.
} else {
// x = 1, y = 0.
x.assign(1, inv(lhs.back()));
y.clear();
}
}
public:
// Class for Finite Field Elements.
struct Element {
const FiniteField* gf;
std::vector<int> a;
// Element initialization as zero.
Element(const FiniteField* gf) : gf(gf), a(gf->k) {}
// Element initialization from the numeric representation.
Element(const FiniteField* gf, int id) : gf(gf), a(gf->k) {
for (int i = 0; i < gf->k; ++i) {
a[i] = id % gf->p;
id /= gf->p;
}
}
// Generate the numeric representation from an element.
int idx() const {
int id = 0;
for (int i = gf->k - 1; i >= 0; --i) {
id = id * gf->p + a[i];
}
return id;
}
// Access the i-th coefficient.
int& operator[](int i) { return a[i]; }
// Addition.
Element& operator+=(const Element& rhs) {
for (int i = 0; i < gf->k; ++i) {
a[i] += rhs.a[i];
if (a[i] >= gf->p) a[i] -= gf->p;
}
return *this;
}
// Addition.
Element operator+(const Element& rhs) const {
Element res(*this);
res += rhs;
return res;
}
// Subtraction.
Element& operator-=(const Element& rhs) {
for (int i = 0; i < gf->k; ++i) {
a[i] -= rhs.a[i];
if (a[i] < 0) a[i] += gf->p;
}
return *this;
}
// Subtraction.
Element operator-(const Element& rhs) const {
Element res(*this);
res -= rhs;
return res;
}
// Multiplication by a scalar.
Element& operator*=(int x) {
for (int i = 0; i < gf->k; ++i) {
a[i] = (long long)a[i] * x % gf->p;
}
return *this;
}
// Multiplication by a scalar.
Element operator*(int x) const {
Element res(*this);
res *= x;
return res;
}
// Multiplication by x.
Element& shift() {
long long d = gf->p - a.back(); // d = -a[k-1].
for (int i = gf->k - 1; i >= 0; --i) {
a[i] = ((i ? a[i - 1] : 0) + d * gf->mod[i]) % gf->p;
}
return *this;
}
// Multiplication.
Element& operator*=(const Element& rhs) {
Element prod(*this);
*this *= rhs.a[0];
for (int j = 1; j < gf->k; ++j) {
prod.shift();
*this += prod * rhs.a[j];
}
return *this;
}
// Multiplication.
Element operator*(const Element& rhs) const {
Element res(*this);
res *= rhs;
return res;
}
// Binary exponentiation.
Element pow(int b) const {
Element res(gf, 1);
Element po(*this);
while (b) {
if (b & 1) res *= po;
po = po * po;
b >>= 1;
}
return res;
}
// Multiplicative inverse.
Element inv() const {
Element res(gf);
auto& x = res.a;
std::vector<int> y;
auto lhs = a;
trim(lhs);
auto rhs = gf->mod;
gf->poly_ex_gcd(lhs, rhs, x, y);
x.resize(gf->k);
return res;
}
// Division.
Element& operator/=(const Element& rhs) {
*this *= rhs.inv();
return *this;
}
// Division.
Element operator/(const Element& rhs) const {
Element res(*this);
res /= rhs;
return res;
}
};
private:
// Check whether the current MOD is irreducible.
bool checkIrreducible() const {
Element f(this, p);
for (int j = 1; j < k; ++j) {
// F = X^{p^j} mod MOD.
f = f.pow(p);
// G = X^{p^j}-X mod MOD.
auto g = f.a;
g[1] = g[1] ? g[1] - 1 : p - 1;
trim(g);
// H = MOD.
auto h = mod;
// Reducible if deg(GCD(G,H))>0.
if (poly_gcd(h, g).size() > 1) return false;
}
return true;
}
public:
FiniteField(int p, int k) : p(p), k(k), mod(k + 1, 1) {
do { // Randomly generate a polynomial.
for (int i = 0; i < k; ++i) {
mod[i] = rand() % p;
}
} while (!checkIrreducible());
}
};
int main() {
int p = 13331, k = 50;
FiniteField gf(p, k);
FiniteField::Element e1(&gf, rand() + 1);
FiniteField::Element e2(&gf, rand() + 1);
FiniteField::Element e3(&gf, rand() + 1);
// Test Frobenius endomorphism.
std::cout
<< ((e1 * e2 + e3).pow(p) - e1.pow(p) * e2.pow(p) - e3.pow(p)).idx();
// Test inverse.
std::cout << ((e1 * e2).inv() - e1.inv() / e2).idx();
return 0;
}
Finite fields of characteristic are the most commonly used in cryptography. For such finite fields, elements can be stored as 01 strings, and operations in the field can be implemented using bitwise operations.
Applications
This section lists some applications of field extensions in algorithmic competitions. The main situation is when, while evaluating an arithmetic expression over a field, we need to introduce intermediate elements that do not originally exist in the field, thereby making direct computation possible. Readers should be familiar with solving real-number problems using complex numbers; this is an example of an extension of the real field; what readers may be less familiar with is extension over finite fields. Therefore, we focus here on extensions of finite fields, especially extensions of the prime field .
In some cases, field extensions can reduce computational complexity and are therefore necessary, such as the fast Fourier transform over the real field; in other cases, a field extension is merely one of many ways to solve a problem, and a method with similar complexity can usually avoid using a field extension, such as the computation of the Fibonacci sequence discussed next. While understanding these applications, readers should compare the advantages and disadvantages of the different methods so that they can choose an appropriate method when solving problems.
Fibonacci sequence
For computing the Fibonacci sequence, common methods include the linear recurrence and matrix exponentiation by squaring. In fact, it can also be solved using a field extension, with the same time complexity . The Fibonacci sequence has the closed-form formula:
We now compute the value of modulo a prime 9. Translating this problem into a computation over the finite field , the first issue is the meaning of in . Algebraically, it is a square root of the element . Therefore, if in there exists a square root of , that is, if is a quadratic residue modulo , we can compute the square root and substitute it directly; otherwise, we need to compute in the extension .
Of course, when computing in an extension, it is not necessary to adjoin specifically. For example, for the Fibonacci sequence, we can let be a root of the polynomial , so that can be written as
If is not a quadratic residue modulo , then the polynomial is irreducible. We can then compute in the extension and obtain the same result as above.
The method for computing the Fibonacci sequence can of course be generalized to other situations. However, one point deserves attention: the irreducibility of polynomials over finite fields does not agree with that over the field of rational numbers. For example, is irreducible over , and its splitting field is ; however, in , if and are both quadratic nonresidues modulo , it is a product of two irreducible polynomials, so in the extension field the square root already exists and no further extension is needed.
Extensions to Rings
As the previous section demonstrated, field extensions have various limitations. For computing the Fibonacci sequence, using only field-extension methods can handle only the case where the modulus is prime and is a quadratic nonresidue modulo . However, the discussion in the section on algebraic extensions shows that if division is not required in the extended structure, rings can also be extended10. This section briefly discusses this method using the computation of the Fibonacci sequence under an arbitrary modulus as an example. Other common situations that do not involve much division, including determinant computation and the fast Fourier transform, can also make use of this method when appropriate.
Let be any positive integer, and let be the -th term of the Fibonacci sequence. The problem is to compute the value of . In principle, this requires computation in . However, as the previous section showed, the reducibility of the polynomial and whether it has repeated roots differ for different moduli, so the closed form of the Fibonacci sequence may differ greatly. Moreover, if itself is not a field, elements in the extension often do not have valid inverses (for example, modulo , the denominator is simply zero). Despite these many problems, under the condition that coefficients are reduced modulo , it actually suffices to compute the remainder
and take its constant term. Comparing this with the closed form above, the rationale for this approach is clear: this seems to be computing inside the “extension”
where is a root of .
Although it is less obvious, this method is also valid. Note that in the extension of the rational field, the closed form holds. This means that in ,
holds. This involves only polynomials with integer coefficients, and therefore it also holds in . Writing it as a polynomial-division-with-remainder identity and reducing the coefficients on both sides modulo gives an identity in . This conclusion holds for every .
In general, if an expression can be computed in an extension of the rational field , then clearing denominators can always yield a conclusion in , and reducing modulo then gives a conclusion in . The key to making this idea work is that clearing denominators must not cause an “irreversible” consequence. For example, when computing the Fibonacci sequence, if instead of using the coefficient of the constant term we use the coefficient of the linear term, then because the coefficient has a factor of , has no inverse when is even, so there is no way to recover the value of ; likewise, for the Fibonacci sequence, if we use a closed-form formula containing a term, clearing denominators introduces factors that are difficult to handle, so it is impossible to draw a conclusion from the result after taking remainders. Therefore, the choice of computation process is crucial to applying this technique.
Cipolla Algorithm
This is a typical example of using an extension of a finite field for computation. For a modulus , consider a quadratic residue , and find its square root by solving for . Although this is a problem over , the Cipolla algorithm performs the computation over the finite field . This section explains the algorithm in the language of field theory. An elementary number-theoretic proof can be found at the linked page.
Specifically, the Cipolla algorithm first chooses such that is a quadratic nonresidue modulo , which means that is irreducible. Thus, letting , we can consider the extension . Because the Frobenius endomorphism can only map an element to its conjugate, and such a conjugate is unique in a quadratic extension, we have . Therefore, . Hence, to determine the square root, it suffices to compute . This value must lie in , because the splitting field of is itself.
Exercises
Finally, we list some problems that directly apply the content of this article, to deepen understanding. However, note that much of the content is not a standard topic in algorithm competitions.
- Cyclotomic polynomials:
- Finite fields:
- Field extensions:
References and Notes
- Dummitt, D.S. and Foote, R.M. (2004) Abstract Algebra. 3rd Edition, John Wiley & Sons, Inc.
- Milne, J.S. Fields and Galois Theory.
- Factorization of polynomials - Wikipedia
- Factorization of polynomials over finite fields - Wikipedia
- Cyclotomic Polynomial - Wikipedia
- Brett Porter's Notes on Cyclotomic Polynomials
- Jordan Bell's Notes on Cyclotomic Polynomials
- Michel Waldschmidt. An introduction to the theory of finite fields
- Finite Field Arithmetic - Wikipedia
Footnotes
-
This is because the field 's multiplicative identity must satisfy the relation over given by , and the latter has only two roots in the field : and , while the definition of a field requires , so it follows that and . ↩
-
In category-theoretic language, this says that is the initial object in the category of rings with identity. ↩
-
Strictly speaking, this refers to the polynomial ring and its universal property (universal property). ↩
-
This polynomial ring has infinitely many indeterminates. To define such a polynomial ring, one must first define monomials. Let the set of indeterminates be , and let its monomials be all functions that are nonzero at only finitely many indeterminates and can be written as , where are the indices of all indeterminates at which is nonzero. A polynomial is a linear combination of finitely many monomials. Under the corresponding addition and multiplication operations, they form a ring. For the case of finitely many indeterminates, one can prove that this definition agrees with the result obtained from the recursive definition in the section on multivariable polynomial rings. ↩
-
Although it is called the fundamental theorem of algebra, this result is not purely algebraic, because constructing the real field requires a topological structure. ↩
-
This statement is not fully precise, because irreducible factors of degrees are also obtained. However, because algorithm implementations usually separate factors starting from smaller degrees, when separating an irreducible polynomial factor of degree , the smaller factors should already have been separated, so the statement is acceptable. ↩
-
Do not confuse this name with the primitive polynomial in polynomial theory (that is, a polynomial whose coefficients have greatest common divisor one). ↩
-
For example, the appendix of Hansen, T., & Mullen, G. L. (1992). Primitive polynomials over finite fields. Mathematics of computation, 59(200), 639-643 provides such a list. ↩
-
When , the characteristic equation of the Fibonacci sequence has a repeated root , so over , the closed-form formula for the Fibonacci sequence is . ↩
-
The phrase “extension of a ring” usually has two meanings: one is a generalization of a group extension, and the other is a generalization of a field extension. This article uses the second meaning. More specifically, the extensions considered in this section are integral extensions of commutative rings with identity, and this is the generalization of the concept of algebraic extensions of fields to commutative rings with identity. ↩