Let be an integral domain and let
be arbitrary polynomials with . Let us give a necessary and sufficient condition for and sharing a common root in .
If is a field, then is a Euclidean domain. Recall that we call an integral domain Euclidean together with the function if for all , there exist such that , where or ; furthermore, for all , we have . The element is called the quotient and is called the remainder. If we are working in a Euclidean domain, we would like the greatest common divisor to be unique. For this, a unique element has to be chosen from each equivalence class obtained by multiplying by the units of the ring . (For example, in case of integers we always choose the non-negative one from the classes ) Thus, every element has a unique form
where is called the normal form of . Let us consider a Euclidean domain over a field . Let the normal form of be the corresponding normalised monic polynomial, that is, , where denotes the leading coefficient of polynomial . Let us summarise these important cases:
If then and ,
if ( is a field) then (the leading coefficient of polynomial with the convention ), and .
The following algorithm computes the greatest common divisor of two arbitrary elements of a Euclidean domain. Note that this is one of the most ancient algorithms of the world, already known by Euclid around 300 B.C.
1 2 3
DO5 6 7
In the ring of integers, the remainder in line 4 becomes . When , where is a field, the remainder in line 4 can be calculated by the algorithm
, the analysis of which is left to Exercise 6.2-1.
Figure 6.2 shows the operation of the
algorithm in and . Note that in the program only enters the while loop with non-negative numbers and the remainder is always non-negative, so the normalisation in line 7 is not needed.
Before examining the running time of the
algorithm, we deal with an extended version of it.
1 2 3
DO5 6 7 8 9 10
Figure 6.2. Illustration of the operation of the
algorithm in and . In case (a), the input is . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines and is executed four times, values , and in these iterations are shown in the table. The
algorithm outputs as result. In case (b), the input parameters are . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial .
It is known that in the Euclidean domain , the greatest common divisor of elements can be expressed in the form with appropriate elements . However, this pair is not unique. For if are appropriate, then so are and for all :
algorithm is completed in a way that beside the greatest common divisor it outputs an appropriate pair as discussed above.
Let , where is a Euclidean domain together with the function . The equations
are obviously fulfilled due to the initialisation in the first two lines of the pseudocode
. We show that equations (6.3) are invariant under the transformations of the while loop of the pseudocode. Let us presume that the conditions (6.3) are fulfilled before an iteration of the loop. Then lines 4–5 of the pseudocode imply
hence, because of lines 6–7,
Lines 8–9 perform the following operations: take the values of and , then take the values of and , while takes the value of and . Thus, the equalities in (6.3) are also fulfilled after the iteration of the while loop. Since in each iteration of the loop, the series obtained in lines 8–9 is a strictly decreasing series of natural numbers, so sooner or later the control steps out of the while loop. The greatest common divisor is the last non-zero remainder in the series of Euclidean divisions, that is, in lines 8–9.
The values of the variables before the execution of line are
The return values are:
We can see that the size of the coefficients show a drastic growth. One might ask why we do not normalise in every iteration of the while loop? This idea leads to the normalised version of the Euclidean algorithm for polynomials.
1 2 3 4 5
DO7 8 9 10 11 12 13 14
Before the execution of line of the pseudocode, the values of the variables are
Looking at the size of the coefficients in, the advantage of the normalised version is obvious, but we could still not avoid the growth. To get a machine architecture-dependent description and analysis of the
algorithm, we introduce the following notation. Let
where is the word length of the computer in bits. It is easy to verify that if and , then
We give the following theorems without proof.
Can the growth of the coefficients be due to the choice of our polynomials? Let us examine a single Euclidean division in the
algorithm. Let , where
and are monic polynomials, , , , and consider the case . Then
Note that the bound (6.6) is valid for the coefficients of the remainder polynomial as well, that is, . So in case , the size of the coefficients may only grow by a factor of around three in each Euclidean division. This estimate seems accurate for pseudorandom polynomials, the interested reader should look at Problem 6-1. The worst case estimate suggests that
where denotes the running time of the
algorithm, practically, the number of times the while loop is executed. Luckily, this exponential growth is not achieved in each iteration of the loop, and altogether the growth of the coefficients is bounded polynomially in terms of the input. Later we will see that the growth can be eliminated using modular techniques.
Summarising: after computing the greatest common divisor of the polynomials ( is a field), and have a common root if and only if their greatest common divisor is not a constant. For if is not a constant, then the roots of are also roots of and , since divides and . On the other hand, if and have a root in common, then their greatest common divisor cannot be a constant, since the common root is also a root of it.
If is a UFD (unique factorisation domain, where every non-zero, non-unit element can be written as a product of irreducible elements in a unique way up to reordering and multiplication by units) but not necessarily a Euclidean domain then, the situation is more complicated, since we may not have a Euclidean algorithm in . Luckily, there are several useful methods due to: (1) unique factorisation in , (2) the existence of a greatest common divisor of two or more arbitrary elements.
The first possible method is to perform the calculations in the field of fractions of . The polynomial is called a primitive polynomial if there is no prime in that divides all coefficients of . A famous lemma by Gauss says that the product of primitive polynomials is also primitive, hence, for the primitive polynomials , if and only if , where denotes the field of fractions of . So we can calculate greatest common divisors in instead of . Unfortunately, this approach is not really effective because arithmetic in the field of fractions is much more expensive than in .
A second possibility is an algorithm similar to the Euclidean algorithm: in the ring of polynomials in one variable over an integral domain, a so-called pseudo-division can be defined. Using the polynomials (6.1), (6.2), if , then there exist , such that
where or . The polynomial is called the pseudo-quotient of and and is called the pseudo-remainder. The notation is .
On the other hand, each polynomial can be written in a unique form
up to a unit factor, where and are primitive polynomials. In this case, is called the content, is called the primitive part of . The uniqueness of the form can be achieved by the normalisation of units. For example, in the case of integers, we always choose the positive ones from the equivalence classes of .
The following algorithm performs a series of pseudo-divisions. The algorithm uses the function , which computes the pseudo-remainder, and it assumes that we can calculate greatest common divisors in , contents and primitive parts in . The input is , where is a UFD. The output is the polynomial .
1 2 3
DO5 6 7 8 9
The operation of the algorithm is illustrated by Figure 6.3. The running time of the
algorithm is the same as the running time of the previous versions of the Euclidean algorithm.
Figure 6.3. The illustration of the operation of the
algorithm with input . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines and is executed three times, the table shows the values of , and in the iterations. In line , variable equals . The
algorithm returns as result.
algorithm is very important because the ring of multivariate polynomials is a UFD, so we apply the algorithm recursively, e.g. in , using computations in the UFDs . In other words, the recursive view of multivariate polynomial rings leads to the recursive application of the
algorithm in a straightforward way.
We may note that, like above, the algorithm shows a growth in the coefficients.
Let us take a detailed look at the UFD . The bound on the size of the coefficients of the greatest common divisor is given by the following theorem, which we state without proof.
Proof. The greatest common divisor of and obviously divides both and , and its degree is at most the minimum of their degrees. Furthermore, the leading coefficient of the greatest common divisor divides and , so it also divides .
Example 6.6 Corollary 6.4 implies that the absolute value of the coefficients of the greatest common divisor is at most for the polynomials (6.4), (6.5), and at most for the polynomials (6.7) and (6.8).
The following method describes the necessary and sufficient conditions for the common roots of (6.1) and (6.2) in the most general context. As a further advantage, it can be applied to solve algebraic equation systems of higher degree.
Let be an integral domain and its field of fractions. Let us consider the smallest extension of over which both of (6.1) and of (6.2) splits into linear factors. Let us denote the roots (in ) of the polynomial by , and the roots of by . Let us form the following product:
It is obvious that equals to if and only if for some and , that is, and have a common root. The product is called the resultant of the polynomials and . Note that the value of the resultant depends on the order of and , but the resultants obtained in the two ways can only differ in sign.
Evidently, this form of the resultant cannot be applied in practice, since it presumes that the roots are known. Let us examine the different forms of the resultant. Since
Although it looks a lot more friendly, this form still requires the roots of at least one polynomial. Next we examine how the resultant may be expressed only in terms of the coefficients of the polynomials. This leads to the Sylvester form of the resultant.
Multiply these equations by the numbers , and , respectively. We get equations from the first one and from the second one. Consider these equations as a homogeneous system of linear equations in indeterminates. This system has the obviously non-trivial solution . It is a well-known fact that a homogeneous system with as many equations as indeterminates has non-trivial solutions if and only if its determinant is zero. We get that and can only have common roots if the determinant
equals to (there are 0s everywhere outside the dotted areas). Thus, a necessary condition for the existence of common roots is that the determinant of order is 0. Below we prove that equals to the resultant of and , hence, is also a sufficient condition for common roots. The determinant (6.9) is called the Sylvester form of the resultant.
Proof. We will precede by induction on . If , then , so the right-hand side is . The left-hand side is a determinant of order with everywhere in the diagonal, and 0 everywhere else. Thus, , so the statement is true. In the following, presume that and the statement is true for . If we take the polynomial
instead of , then and fulfil the condition:
Since , the coefficients of and satisfy
We transform the determinant in the following way: add times the first column to the second column, then add times the new second column to the third column, etc. This way the -s disappear from the first lines, so the first lines of and the transformed are identical. In the last rows, subtract times the second one from the first one, and similarly, always subtract times a row from the row right above it. In the end, becomes
Using the last row for expansion, we get , which implies by the induction hypothesis.
We get that , that is, polynomials and have a common root in if and only if determinant vanishes.
From an algorithmic point of view, the computation of the resultant in Sylvester form for higher degree polynomials means the computation of a large determinant. The following theorem implies that pseudo-division may simplify the computation.
Proof. Multiply the first line of the determinant (6.9) by . Let and be the uniquely determined polynomials with
where . Then multiplying row of the resultant by , row by etc., and subtracting them from the first row we get the determinant
Here is in the th column of the first row, and is in the th column of the first row.
Similarly, multiply the second row by , then multiply rows by etc., and subtract them from the second row. Continue the same way for the third, th row. The result is
After reordering the rows
Equation (6.10) describes an important relationship. Instead of computing the possibly gigantic determinant , we perform a series of pseudo-divisions and apply (6.10) in each step. We calculate the resultant only when no more pseudo-division can be done. An important consequence of the theorem is the following corollary.
Using the last column for expansion and factoring and , we get the statement with the restrictions on the degrees.
The most important benefit of the resultant method, compared to the previously discussed methods, is that the input polynomials may contain symbolic coefficients as well.
Then the existence of common rational roots of and cannot be decided by variants of the Euclidean algorithm, but we can decide it with the resultant method. Such a root exists if and only if
that is, when or .
The significance of the resultant is not only that we can decide the existence of common roots of polynomials, but also that using it we can reduce the solution of algebraic equation systems to solving univariate equations.
Consider polynomials and as elements of . They have a common root if and only if
We note that the resultant method can also be applied to solve polynomial equations in several variables, but it is not really effective. One problem is that computational space explosion occurs in the computation of the determinant. Note that computing the resultant of two univariate polynomials in determinant form using the usual Gauss-elimination requires operations, while the variants of the Euclidean algorithm are quadratic. The other problem is that computational complexity depends strongly on the order of the indeterminates. Eliminating all variables together in a polynomial equation system is much more effective. This leads to the introduction of multivariate resultants.
All methods considered so far for the existence and calculation of common roots of polynomials are characterised by an explosion of computational space. The natural question arises: can we apply modular techniques? Below we examine the case with . Let us consider the polynomials (6.4), (6.5) and let a prime number. Then the series of remainders in in the
We get that polynomials and are relatively prime in . The following theorem describes the connection between greatest common divisors in and .
(2) if , then .
By the hypothesis , which implies
(2): Since and is non-trivial,
If , then the right-hand side of (6.13) is non-trivial, thus . But the resultant is the sum of the corresponding products of the coefficients, so , contradiction.
In case statement (1) of Theorem 6.8 is fulfilled, we call a “lucky prime'”. We can outline a modular algorithm for the computation of the gcd.
1 the Landau-Mignotte constant (from Corollary 6.4) 2 3
DOa prime with , , and 5 6
The first line of the algorithm requires the calculation of the Landau-Mignotte bound. The fourth line requires a “sufficiently large” prime which does not divide the leading coefficient of and . The fifth line computes the greatest common divisor of polynomials and modulo (for example with the
algorithm in ). We store the coefficients of the resulting polynomials with symmetrical representation. The sixth line examines whether and are fulfilled, in which case is the required greatest common divisor. If this is not the case, then is an “unlucky prime”, so we choose another prime. Since, by Theorem 6.8, there are only finitely many “unlucky primes”, the algorithm eventually terminates. If the primes are chosen according to a given strategy, set is not needed.
The disadvantage of the
algorithm is that the Landau-Mignotte constant grows exponentially in terms of the degree of the input polynomials, so we have to work with large primes. The question is how we could modify the algorithm so that we can work with “many small primes”. Since the greatest common divisor in is only unique up to a constant factor, we have to be careful with the coefficients of the polynomials in the new algorithm. So, before applying the Chinese remainder theorem for the coefficients of the modular greatest common divisors taken modulo different primes, we have to normalise the leading coefficient of . If and are the leading coefficients of and , then the leading coefficient of divides . Therefore, we normalise the leading coefficient of to in case of primitive polynomials and ; and finally take the primitive part of the resulting polynomial. Just like in the
algorithm, modular values are stored with symmetrical representation. These observations lead to the following modular gcd algorithm using small primes.
1 2 a prime such that 3 4 5 6 7 8
RETURN17 a prime such that and 18 19 20 21
1 2 3
DO5 6 7
We may note that the algorithm
does not require as many small primes as the Landau-Mignotte bound tells us. When the value of polynomial does not change during a few iterations, we test in lines 13–16 if is a greatest common divisor. The number of these iterations is stored in the variable of line six. Note that the value of could vary according to the input polynomial. The primes used in the algorithms could preferably be chosen from an (architecture-dependent) prestored list containing primes that fit in a machine word, so the use of set becomes unnecessary. Corollary 6.9 implies that the
algorithm always terminates.
algorithm computes the solution of the equation system obtained by taking congruence relations modulo and for the coefficients of identical degree in the input polynomials and . This is done according to the Chinese remainder theorem. It is very important to store the results in symmetrical modular representation form.
After the execution of the first six lines of the algorithm with , we have and . Since due to line 7, lines 10–12 are executed. Polynomial is not zero, so , and will be the values after the execution. The condition in line 13 is not fulfilled, so we choose another prime, is a bad choice, but is allowed. According to lines 19–20, , . Since , we have and lines 25–30 are not executed. Polynomial is constant, so the return value in line 11 is 1, which means that polynomials and are relatively prime.
Let again . After the first six lines of the polynomials . After the execution of lines 10–12, we have . Let the next prime be . So the new values are . Since , and the new value of is after lines 25–30. The value of the variable is still 1. Let the next prime be 11. Then . Polynomials and have the same degree, so we modify the coefficients of . Then and since , we get and . Let the new prime be 13. Then . The degrees of and are still equal, thus lines 25–30 are executed and the variables become .After the execution of lines 17–18, it turns out that and , so is the greatest common divisor.
We give the following theorem without proof.
algorithm works correctly. The computational complexity of the algorithm is machine word operations, where , and is the Landau-Mignotte bound for polynomials and .
ELSE7 and 8
Prove that the algorithm uses at most
operations in .
6.2-2 What is the difference between the algorithms
6.2-3 Prove that .
6.2-4 The discriminant of polynomial (, ) is the element
where denotes the derivative of with respect to . Polynomial has a multiple root if and only if its discriminant is 0. Compute for general polynomials of second and third degree.