https://doi.org/10.53656/math2024-4-3-ani

2024/4, стр. 392 - 405

AN ITERATIVE ALGORITHM FOR DETERMINING THE GREATEST COMMON DIVISOR OF TWO OR MORE UNIVARIATE POLYNOMIALS

Резюме: The GCD problem in polynomial rings has long intrigued mathematicians for its diverse applications, leading to methods like the Euclidean algorithm, Routh array, and matrix-based approaches. Despite the low costs of the Euclidean algorithm, it faces numerical instability, while matrix-based techniques, though stable, involve higher computational expenses. The goal of this paper is to introduce a novel approach to determining the greatest common divisor (GCD) of multiple polynomials in a single variable, particularly suitable for interdisciplinary teaching in mathematics and programming. Our methodology involves iterating through the entire set of polynomials directly, aiming to enhance the procedure's efficiency while maintaining low computational costs. Numerous examples are provided to illustrate its practical application in teaching, ranging from easy to challenging scenarios, as well as Python implementation of the given procedure.

Ключови думи: greatest common divisor; univariate polynomials; algorithm; Python program

1. Introduction

The issue of determining the greatest common divisor (GCD) of two or more members of a polynomial ring has long attracted the attention of mathematicians, and it has a wide range of applications (Christou et al. 2011; Pace & Barnett 1973). Over the years different methods have been developed. Some of them are the Euclidien algorithm, Routh’s array algorithm (Fryer 1959), Barnett’s use of the companion matrix (Barnett 1970), Blankinship’s matrix methods (Blankinship 1963), Weinstock’s iterative method (Pace & Barnett 1973; Weinstock 1960), Extended Row Equivalence and Shifting operations (ERES) method (Christou et al. 2010; Karcanias 1987), and a lot of different matrix methods (Boito 2012; Christou et al. 2017; Christou et al. 2011; Mitrouli & Karcanias 1993). The basic Euclidean algorithm is computationally efficient, with a cost that scales quadratically with the degree of the input polynomials. However, it suffers from numerical instability. However, while the majority of matrix-based variants are numerically stable, they often have higher than quadratic computational costs (Boito 2012).

Any method that works for two polynomials may be adapted to work for more. However, the fact that we typically have to deal with a high number of polynomials is a key difficulty for some applications of the GCD, and the pairwise type techniques for GCD (Blankinship 1963) are not suited for such applications. Matrix-based approaches tend to have higher performance and numerical stability, especially when dealing with large sets of polynomials, due to the usage of the complete set of polynomials. In this paper, based on algorithm developed by Prešić (Prešić 1997) that refers to systems of two algebraic equations, we have come to an iterative new algorithm for finding GCD of more polynomials in one variable simultaneously. The objective is to reduce computation costs while achieving improved performance and numerical stability. The main advantage of the presented method is that it works with complete set of polynomials directly.

In Section 2 of this paper, we present several definitions, theorems, and lemmas related to our method of computing polynomials’ GCD. This was the mathematical background for the algorithm we developed. A few examples are given in Section 3 along with a practical explanation of how to use this approach to find GCD. The description of the algorithm was provided and computational costs are discussed in Section 4. The Python implementation of the method and the testing outcomes are shown in Section 5. The conclusion with practical implications is presented in Section 6.

2. Mathematical background for calculating greatest common divisor of polynomials

In this section, we provide an overview of the definitions, theorems, and lemmas related to GCD of polynomials.

Let be a commutative ring with identity. Considerations below are for the ring of integers (although the procedure works with some rational coefficients too). Let be the polynomial ring over .

Theorem 1. (Division Algorithm) For any polynomials and ! polynomials and , where either or .

We denote traditionally when .

Definition 1. A monic polynomial is called greatest common divisor (GCD) of and iff , and . Remark A monic polynomial is a polynomial with only one variable whose leading coefficient is equal to 1.

In this paper the greatest common divisor of and is denoted by or . If , then the polynomials and are said to be relatively prime.

Lemma 1. Let be any nonzero p olynomials. Then

The Euclidean algorithm for finding GCD of two polynomials actually represents a special case of Lemma 1 when for two nonzero polynomials and and or ) , we choose such that is division remainder of polynomial with polynomial . In this case:

• If then divides and f for some constant .

• If then it is easy to show that .

The Euclidean algorithm continually implements the special case of Lemma 1 and the division algorithm to achieve a remainder equal to 0. The degrees of the polynomials are decreasing while the procedure is repeated, and the GCD of the two polynomials may then be calculated in a limited number of steps.

Lemma 2. Let be nonzero p olynomials. Then we have:

where i is a polynomial of minimal degree among .

Let us denote by rem( ),q(x)) the remainder of the division of by the polynomial . Then a special case of Lemma 2 would be:

3. New method for determining the GCD of two or more univariate polynomials

Let the set of polynomials , is given and corresponding degrees of the polynomials are . The set will be called an -ordered polynomial set. This section provides detailed explanations of our method using examples.

Task. Find the GCD of the following sets of polynomials in :

a. ; b. ; c. ;

d. , .

Instruction. The method we will employ to calculate the GCD of a set of polynomials implements Lemma 2 and the Division algorithm. This method is comparable to Gauss’ algorithm for solving a systems of linear equations. We consider each polynomial of degree of the set as a linear equations with unknowns . In order to obtain the unique GCD of the polynomial set (if there is one) or some non-zero element of (in case the polynomials are relatively prime), we build a chain of equivalences successively for as long as needed.

Solutions:

a) Let us denote .

In this subtask we are dealing with a -ordered polynomial set, where the degrees of polynomials are equal. Rule: when the degrees are equal, the first polynomial will always be retained. So, we multiply the first polynomial by −2 and add the obtained polynomial to the second (like in Gauss elimination). Then, as , based on Lemma 2 we get (multiplying result by in order to simplify it)

It is worth noticing that now, rather than working with two cubic polynomials, we have ”shifted situation down“ to finding the GCD of one cubic and one quadratic polynomial. So, we ”descended“ from a (3, 3)-ordered polynomial set to a -ordered polynomial set.

Now we multiply the second polynomial by (because of the lower degree) and add it to the first:

After multiplying this polynomial by we get

shifting down from a to a set. Because , we have . □

b) Let us denote .

In this subtask we have a set. We rewrite the second polynomial at the first place, and as we get

reducing to a set.

With a similar to the previous step, since , we get

Now, we have an set and as we get The new case is an (1, 0) set but we came to the non-zero value 2 as a second polynomial in the set. This leads to the conclusion that the GCD of our polynomial set is 1, i.e. the polynomials are relatively prime.□

c. Let us denote .

In this subtask we should find the GCD of three univariate polynomials that form an (11, 2, 7) set. First, we find a polynomial of the lowest degree (which is the second). We rewrite it on the first place in the list. Every other polynomial will be replaced by a new one, calculated as in previous examples, except that now we look at the pairs composed of the polynomial with the lowest degree and another one whose turn is for replacement. The new polynomial that we get by transformations of polynomials and is denoted by . The procedure could be written in this way:

.

For the first replacement we obtain and for the second thus we now have and the GCD of the three polynomials is . □

d. Let us denote , ( ) set. The polynomial of the lowest degree is so

Now we calculate three replacements

-

;

-

-

Note that in order to avoid rational coefficients in the second replacement, we multiplied the first polynomial by 2, and second by , and then calculated the addition. And more, we simplify the fourth polynomial multiplying it by and . In this way we got a new ( ) = 5x3 + x2 + 5x + 1. In this way we got a new (3,3,3,3)set. By applying the rule when degrees are equal, the first polynomial is retained, so

We calculate the three replacements:

- , - , - , and after simplifying

Now we got a new -set, where the second, third and fourth polynomials are equal and of the lowest degree. But is simplified to and this is the GCD of the four polynomials.

4. Algorithm for calculating GCD of two or more univariate polynomials

For two polynomials and and and are their monomials of higher degree we define the function .

Let us describe the general procedure for calculating GCD of list of p olynomials of variable and are the degrees of the polynomials. Let us also denote: with – the minimal degree of a polynomial of , with – the ordinal of the current polynomial, and with – the length of the list.

4.1. Algorithm for determining GCD of polynomials

Step 1 (Initialisation). and let (without limiting the generality) the polynomial of degree be .

Step 2 (Outer loop). If then go to Step 3. If then it is the GCD of our polynomials. Otherwise the polynomials are relatively prime. Stop.

Step 3 (Inner loop). Create a new list . Its first polynomial will be . Then loop for to with step 1 and do:

Step 3.1. .

Step 3.2. If push it in and continue.

Step 3.3. If continue, else the polynomials are relatively prime. Stop.

Step 4. Rearrange the elements of in order that the polynomial with smaller degree to be and rename to . Let be the length of . Go to Step 2.

4.2. Complexity of the algorithm

For estimating the complexity of our algorithm we will compare it with the complexity of the Euclidean algorithm for finding GCD of two polynomials and :

where the sign denote the operation finding remainder of modulo .

Suppose we must find GCD of the polynomials of degree and of degree . The Euclidean algorithm generates a sequence of polynomials: