# On Degrees of Modular Common Divisors and the Big Primeg

Authors: Vahagn Mikaelian
Journal: International Journal of Mathematics and Mathematical Sciences
 (2016)

---

## Abstract

We consider a few modifications of the Big prime modularg
c
d algorithm for polynomials in Z
[
x
]. Our modifications are based on bounds of degrees of modular common divisors of polynomials, on estimates of the number of prime divisors of a resultant, and on finding preliminary bounds on degrees of common divisors using auxiliary primes. These modifications are used to suggest improved algorithms for g
c
d calculation and for coprime polynomials detection. To illustrate the ideas we apply the constructed algorithms on certain polynomials, in particular on polynomials from Knuth’s example of intermediate expression swell.


---

## Body

## 1. Introduction

This work is one of the articles in which we would like to present parts from new introduction to computer algebra [1] that currently is under preparation. In [1] we try to give a “more algebraic” and detailed view on some of the areas of computer algebra, such as algorithms on the Euclidean rings, extensions of fields, operators in spaces on finite fields, and factorization in UFDs.The Big prime modularg
c
d algorithm is one of the first and most popular algorithms of computer algebra. In its classical form, it allows calculating the greatest common divisor g
c
d
(
f
(
x
)
,
g
(
x
)
) for any nonzero polynomials f
(
x
)
,
g
(
x
)
∈
Z
[
x
]. There are a few modifications of this algorithm for other UFDs, such as multivariate polynomial rings. Attention to the g
c
d calculation is partially explained by the first examples that were built to explain importance of application of algebraic methods to computer science. In particular, Knuth’s well-known example of intermediate expression swell discusses the polynomials(1)
f
x
=
x
8
+
x
6
-
3
x
4
-
3
x
3
+
8
x
2
+
2
x
-
5
,
g
x
=
3
x
6
+
5
x
4
-
4
x
2
-
9
x
+
21
,and it shows that calculation of g
c
d
(
f
(
x
)
,
g
(
x
)
) by traditional Euclidean algorithm on rational numbers generates very large integers to deal with, whereas consideration of these polynomials modulo p, that is, consideration of their images under ring homomorphism φ
p
:
Z
[
x
]
→
Z
p
[
x
] (where Z
p
[
x
] is the polynomial ring over the residue ring Z
p
≅
Z
/
p
Z) very easily shows that g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
1 (see [2] and also [3–6]). We are going to use polynomials (1) as examples below to apply the algorithms below (see Examples 16, 18, 22, 25, 27, and 29).The main idea of the Big prime modularg
c
d algorithm is that for the given polynomials f
(
x
)
,
g
(
x
)
∈
Z
[
x
] one may first consider their images f
p
(
x
)
=
φ
p
(
f
(
x
)
)
,
g
p
(
x
)
=
φ
p
(
g
(
x
)
)
∈
Z
p
[
x
] under φ
p. Unlike Z
[
x
], the ring Z
p
[
x
] is an Euclidean domain, since it is a polynomial ring over a field, so g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) can be computed in it by the well-known Euclidean algorithm. There remains “to lift” a certain fold t
·
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) of it to the ring Z
[
x
] to reconstruct the preimage g
c
d
(
f
(
x
)
,
g
(
x
)
). The “lifting” procedure consists of selecting the suitable value for prime p, then finding in Z
[
x
] an appropriate preimage for g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
), and then checking if that preimage divides both f
(
x
) and g
(
x
). If yes, it is g
c
d
(
f
(
x
)
,
g
(
x
)
) we are looking for. If not, then a new p need be selected to repeat the process. Arguments based on resultants and on Landau-Mignotte bounds show that we can effectively choose p such that the number of required repetitions is “small.”The first aim of this work is to present in Sections2–5 a slightly modified argumentation of the algorithm, based on comparison of the degrees of common divisors of f
(
x
) and g
(
x
) in Z
[
x
] and of f
p
(
x
) and g
p
(
x
) in Z
p
[
x
] (see Algorithm 2). This approach allows some simplification of a step of the algorithm: for some primes p, we need not reconstruct the preimage of t
·
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
), but we immediately get an indication that this prime is not suitable, and we should proceed to a new p (see Remark 15).Then in Section6 we discuss the problem if the Big prime modular g
c
d algorithm could output the correct answer using just one prime p or not. The answer is positive, but for some reasons it should not be used to improve the algorithm (to make it work with one p) because it evolves a very large prime (see Remark 19). Instead, we show that we can estimate the maximal number of p (repetitions of steps) that may be used in traditional Big prime modular g
c
d algorithm. For example, for polynomials (1) of Knuth’s example, this number is at most 31. Estimates of this type can be found in literature elsewhere. We just make the bound considerably smaller (see Remark 23).The obtained bounds on the number of primesp are especially effective when we are interested not in g
c
d but just in detection if the polynomials f
(
x
)
,
g
(
x
)
∈
Z
[
x
] are coprime or not. We consider this in Section 7 (see Algorithm 3).In Section8 we consider four other ideas to modify the Big prime modular g
c
d algorithm. Two first ideas are based on checking the number of primes p. The third idea is based on using an auxiliary prime q to estimate the degree of g
c
d
(
f
(
x
)
,
g
(
x
)
) by means of the degree of g
c
d
(
f
q
(
x
)
,
g
q
(
x
)
) (see Algorithm 4). Example 27 shows how much better results we may get by this modification. The fourth idea combines both approaches: it uses a set of auxiliary primes q
1
,
…
,
q
k
+
1 to correctly find the degree of g
c
d
(
f
(
x
)
,
g
(
x
)
), and then we use a modified version of Landau-Mignotte bound to find a single big prime p by which we can calculate the g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
).The arguments used here can be generalized for the case of polynomials on general UFDs. From the unique factorization in a UFD, it easily follows thatg
c
d always exists, and it is easy to detect if the given common divisor of maximal degree is g
c
d or not. The less simple part is to find ways to compute g
c
d (without having the prime-power factorization). That can be done for some classes of UFDs, such as multivariate polynomials on fields.


## 2.g
c
d in Polynomial Rings and the Degrees of Common Divisors

The problem of finding the greatest common divisorg
c
d
(
a
,
b
) of any nonzero elements a, b in a ring R can be separated to two tasks:(1)
Finding out ifg
c
d
(
a
,
b
), in general,exists for a
,
b
∈
R.
(2)
Finding aneffective way to calculate g
c
d
(
a
,
b
).The Euclidean algorithm gives an easy answer to both of these tasks in any Euclidean domain, that is, an integrity domainR possessingEuclidean norm  δ
:
R
∖
0
→
N
∪
{
0
}, such that δ
(
a
b
)
≥
δ
(
a
) hold for any nonzero elements a
,
b
∈
R; and for any a
,
b
∈
R, where b
≠
0, there exist elements q
,
r
∈
R, such that a
=
q
b
+
r, where either r
=
0 or r
≠
0 and δ
(
r
)
<
δ
(
b
) [4, 5, 7–10]. The Euclidean algorithm works for any polynomial ring K
[
x
] over a field K, such as Q
[
x
], R
[
x
], C
[
x
], and Z
p
[
x
] because these rings can easily be turned to an Euclidean domain by defining δ
(
f
(
x
)
)
=
d
e
g
f
(
x
) for any nonzero f
(
x
)
∈
K
[
x
].The situation is less simple in non-Euclidean domains, even in such a widely used ring as the ringZ
[
x
] of polynomials with integer coefficients. That Z
[
x
] is not an Euclidean domain easy to show by elements x
,
2
∈
Z
[
x
]. If Z
[
x
] were an Euclidean domain, it would contain elements u
(
x
), v
(
x
) such that x
·
u
(
x
)
+
2
·
v
(
x
)
=
g
c
d
(
x
,
2
)
=
±
1, which is not possible.The first of two tasks mentioned above, namely,existence of g
c
d, can be accomplished for Z
[
x
] by proving that Z
[
x
] is a UFD, that is, an integrity domain in which every nonzero element a has a factorization a
=
ϵ
p
1
⋯
p
k, where ϵ
∈
R
∗ is a unit (invertible) element in R, the elements p
i are prime for all i
=
1
,
…
,
k, and the factorization above is unique in the sense that if a has another factorization of that type θ
q
1
⋯
q
s, where θ
∈
R
∗ and the elements q
i are prime, then k
=
s and (perhaps after some reordering of the prime factors) the respective prime elements are associated: p
i
≈
q
i for all i
=
1
,
…
,
k. For briefness, in the sequel we will often omit the phrase “perhaps after some reordering of the prime factors” and this will cause no confusion.After merging the associated prime elements together, we get a unique factorization into prime-power elements:(2)
a
=
ν
p
1
α
1
⋯
p
n
α
n
,
ν
∈
R
∗
,
α
i
∈
N
,
p
i
≉
p
j
for  any
i
≠
j
;
i
,
j
=
1
,
…
,
n(in some arguments below we may admit that some of the factors p
i
α
i participate with degrees α
i
=
0; this makes some notations simpler). From this, it is easy to see that, in a UFD R, g
c
d
(
a
,
b
) exists for any nonzero elements a
,
b
∈
R. Assume b
∈
R has the factorization (3)
b
=
κ
p
1
α
1
′
⋯
p
n
α
n
′
,
κ
∈
R
∗(we use the same primes p
i in both factorizations because if, e.g., p
i is not actually participating in one of those factorizations, we can add it as p
i
α
i with α
i
=
0). Then(4)
g
c
d
a
,
b
=
d
=
p
1
γ
1
⋯
p
n
γ
n
,where γ
i
=
min
⁡
α
i
,
α
i
′. This follows from uniqueness of factorization in UFD. For, if h is a common divisor of a, b and if p
i is a prime divisor of h, then it also is a prime divisor of a and of b. The elements p
i cannot participate in factorization of h by a power greater than m
i
n
{
α
i
,
α
i
′
}, because then a (or b) would have an alternative factorization in which p
i occurs more than α
i (or α
i
′) times.The shortest way to see thatZ
[
x
] is a UFD is to apply Gauss’s theorem: if the ring R is a UFD, then the polynomial ring R
[
x
] also is a UFD [4, 7, 8, 10, 11]. Since Z is a UFD (that fact is known as “the fundamental theorem of arithmetic”), Z
[
x
] also is a UFD.Clearly,g
c
d
(
a
,
b
) is defined up to a unit multiplier from R
∗. For integers from R
=
Z or for polynomials from R
=
Z
[
x
], this unit multiplier can be just -
1 or 1. So to say, g
c
d
(
a
,
b
) is defined “up to the sign ±
1” because Z
∗
=
Z
[
x
]
∗
=
{
-
1,1
}. And for polynomials from R
=
Z
p
[
x
], g
c
d
(
a
,
b
) is defined up to any nonzero multiplier t
∈
Z
p
∗
=
{
1
,
…
,
p
-
1
}. Taking this into account, we can use g
c
d
(
a
,
b
)
=
1 and g
c
d
(
a
,
b
)
≈
1 as equivalent notations, since associated elements are defined up to a unit multiplier. Notice that in some sources they prefer to additionally introduce a normal form of g
c
d to distinguish one fixed instance of g
c
d. Instead of using that extra term, we will just in a few places refer to the “positive g
c
d,” meaning that we take, for example, 2
=
g
c
d
(
6,8
) and not -
2.Furthermore, since the contentc
o
n
t
f
(
x
) of a polynomial f
(
x
) is g
c
d for some elements (coefficients of the polynomials), the constant and the primitive part p
p
f
(
x
)
=
f
(
x
)
/
c
o
n
t
f
(
x
) can also be considered up to a unit multiplier. For a nonzero polynomial f
(
x
)
∈
Z
[
x
], we can choose c
o
n
t
f
(
x
) so that s
g
n
c
o
n
t
f
(
x
)
=
s
g
n
l
c
f
(
x
); that is, the c
o
n
t
f
(
x
) has the same sign as the leading coefficient of f
(
x
). Then the leading coefficient l
c
p
p
f
(
x
) of the primitive part p
p
f
(
x
)
=
f
(
x
)
/
c
o
n
t
f
(
x
) will be positive. We will use this below without special notification.Now we would like to little restrict the algebraic background we use. Two main algebraic systems, used in the Big prime modularg
c
d algorithm, are the Euclidean domains and the UFDs. However, their usage is “asymmetric” in the sense that the Euclidean domains and Euclidean algorithm are used in many parts of the Big prime modular g
c
d algorithm, whereas the UFDs are used just to prove that g
c
d does exist. Moreover, it is easy to understand that (2) and (4) may hardly be effective tools to calculate g
c
d, since they are using factorization of elements to primes, while finding such a factorization is a more complicated task than finding just g
c
d. Thus, it is reasonable to drop the UFDs from consideration and to obtain (2) directly using Gauss’s lemma on primitive polynomials in Z
[
x
] (a polynomial f
(
x
)
∈
Z
[
x
] is primitive if c
o
n
t
f
(
x
)
≈
1, that is, p
p
f
(
x
)
=
f
(
x
)
/
c
o
n
t
f
(
x
)
≈
f
(
x
)).By Gauss’s lemma, a product of two primitive polynomials is primitive inZ
[
x
] [4, 7, 8, 10, 11]. So if(5)
f
x
=
c
o
n
t
f
x
·
p
p
f
x
,
g
x
=
c
o
n
t
g
x
·
p
p
g
x
,then(6)
c
o
n
t
f
x
·
g
x
=
c
o
n
t
f
x
·
c
o
n
t
g
x
,
p
p
f
x
·
g
x
=
p
p
f
x
·
p
p
g
x
.The following is easy to deduce from Gauss’s lemma.Lemma 1.
Iff
(
x
)
,
t
(
x
)
∈
Z
[
x
] and t
(
x
) is primitive, then if t
(
x
) divides f
(
x
) in the ring Q
[
x
] and then t
(
x
) also divides f
(
x
) in Z
[
x
].The unique factorization of any nonzerof
(
x
)
∈
Z
[
x
] is easy to obtain from decompositions (6) above and from Lemma 1. Let us just outline it; the details can be found in [1, 4, 5, 7, 8]. By the fundamental theorem of arithmetic, c
o
n
t
f
(
x
) can in a unique way be presented as a product of powers of primes: c
o
n
t
f
(
x
)
=
ν
p
1
α
1
⋯
p
n
α
n
. So, if deg
⁡
f
(
x
)
=
0, then we are done.Assumedeg
⁡
f
(
x
)
>
0. If f
(
x
) is not prime, then, by repeatedly splitting it to products of factors of lower degree as many times as needed, we will eventually get a presentation of f
(
x
) as a product of c
o
n
t
f
(
x
) and of some finitely many primitive prime polynomials q
i
(
x
) of degrees greater than 0. We do not yet have the uniqueness of this decomposition, but we can still group the associated elements together to get the presentation(7)
f
x
=
c
o
n
t
f
x
·
p
p
f
x
=
ν
p
1
α
1
⋯
p
n
α
n
·
q
1
β
1
x
⋯
q
m
β
m
x
.If f
(
x
) has another, alternative presentation of this sort and if t
(
x
) is one of the primitive prime factors (of degree greater than 0) of that presentation, then product (7) is divisible by t
(
x
). By Lemma 1, t
(
x
) divides f
(
x
) also in Z
[
x
]. Since t
(
x
) is prime, it is associated with one of q
i
(
x
). Eliminate one instance of this q
i
(
x
) in (7) and consider f
(
x
)
/
q
i
(
x
). If f
(
x
)
/
q
i
(
x
) also is divisible by q
i
(
x
), we repeat the process. If not, we turn to other primitive prime polynomials (of degree greater than 0) dividing what remains from (7) after elimination. After finitely many steps, (7) will become ν
p
1
α
1
⋯
p
n
α
n, and also from the other alternative presentation a constant should be left only. So we apply the fundamental theorem of arithmetic one more time to get that (7) is the unique factorization.We see that (7) is a particular case of (2). The proof above avoided usage of Gauss’s theorem and the formal definitions of the UFDs. And we see that the prime elements of Z
[
x
] are of two types:prime numbers andprimitive prime polynomials of degrees greater than 0.Existence ofg
c
d
(
f
(
x
)
,
g
(
x
)
) for any two nonzero polynomials in f
(
x
)
,
g
(
x
)
∈
Z
[
x
] can be deduced from (7) in analogy with (4). If(8)
g
x
=
ν
′
p
1
α
1
′
⋯
p
n
α
n
′
·
q
1
β
1
′
x
⋯
q
m
β
m
′
x
,then(9)
g
c
d
f
x
,
g
x
=
κ
p
1
γ
1
⋯
p
n
γ
n
·
q
1
δ
1
x
⋯
q
m
δ
m
x
,where κ
=
±
1, γ
i
=
min
⁡
{
α
i
,
α
i
′
}, and δ
j
=
min
⁡
β
j
,
β
j
′ (i
=
1
,
…
,
n
;
j
=
1
,
…
,
m). However, like we admitted earlier, (4) and (9) are no effective tools to calculate g
c
d. We will turn to g
c
d calculation algorithm in the next sections (see Algorithms 4 and 5).Equations (4) and (9) allow us to get some information that will be essential later. Observe that the following definition of g
c
d, often used in elementary mathematics, is no longer true for general polynomial rings:“
d
(
x
)
is the greatest common divisor of
f
(
x
)
and
g
(
x
)
if it is their common divisor of maximal degree.” For example, for f
(
x
)
=
12
x
2
+
24
x
+
12 and g
(
x
)
=
8
x
+
8, the maximum of degree of their common divisors is 1. Nevertheless, h
(
x
)
=
x
+
1 is not g
c
d
(
f
(
x
)
,
g
(
x
)
), although h
(
x
)
∣
f
(
x
), h
(
x
)
∣
g
(
x
), and deg
⁡
h
(
x
)
=
1. For, x
+
1 is not divisible by the common divisor 2
x
+
2. We can detect the cases when the divisor of highest degree is g
c
d.Lemma 2.
For polynomialsf
(
x
)
,
g
(
x
)
∈
Z
[
x
], their common divisor of maximal degree h
(
x
) is their g
c
d if and only if c
o
n
t
h
(
x
)
≈
g
c
d
(
c
o
n
t
f
(
x
)
,
c
o
n
t
g
(
x
)
).The lemma easily follows from (7), (8), and (9). We see that in example above the condition was missing: c
o
n
t
x
+
1
=
1 but g
c
d
(
c
o
n
t
f
(
x
)
,
c
o
n
t
g
(
x
)
)
=
g
c
d
(
12,8
)
≈
4
≉
1. In fact, g
c
d
(
f
(
x
)
,
g
(
x
)
)
≈
4
x
+
4.Corollary 3.
For primitive polynomialsf
(
x
)
,
g
(
x
)
∈
Z
[
x
], their common divisor of maximal degree h
(
x
) is their g
c
d if and only if h
(
x
) is primitive.In the case if polynomials are over a field, the situation is simpler. For any fieldK, the polynomial ring K
[
x
] is a UFD (and even an Euclidean domain). Any nonzero f
(
x
)
∈
K
[
x
] has a factorization(10)
f
x
=
θ
·
q
1
β
1
x
⋯
q
m
β
m
x
,
θ
∈
K
∗
,
deg
⁡
q
i
x
>
0
,
i
=
1
,
…
,
m
,which is unique in the sense mentioned above. Since all nonzero scalars in K are units, what we, in (7) above, had as a product of some prime numbers actually “merges” in K into a unit: (11)
ν
·
p
1
α
1
⋯
p
n
α
n
=
θ
∈
K
∗
=
K
∖
0
.Comparing factorizations of type (10) for any nonzero polynomials f
(
x
)
,
g
(
x
)
∈
K
[
x
], we easily get the following.Lemma 4.
For any nonzero polynomialsf
(
x
)
,
g
(
x
)
∈
K
[
x
] over a field K, their common divisor of maximal degree h
(
x
) is their g
c
d.This, in particular, is true for rings mentioned above:Q
[
x
], R
[
x
], C
[
x
], and Z
p
[
x
]. We will use this fact later to construct the Big prime modular g
c
d algorithm and its modifications.The analog of Lemma4 was not true for Z
[
x
] because in factorization (9) we have the nonunit prime-power factors p
i
γ
i which do participate in factorization of d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
) but which addnothing to the degree of d
(
x
). This is why maximality of the degree is no longer the only criterion in Z
[
x
] to detect if the given h
(
x
) is g
c
d or not.


## 3. Some Notations for Modular Reductions

The following notations, adopted from [1], are to make our arguments shorter and more uniform when we deal with numerals, polynomials, and matrices. As above, let Z
p be the residue ring (finite Galois field Z
p
=
F
p
=
{
0
,
…
,
p
-
1
}) and let (12)
φ
p
:
Z
⟶
Z
pbe the rings homomorphism mapping each z
∈
Z to the remainder after division of z by p. That is, φ
p
(
z
)
≡
z
(
mod
⁡
p
), and φ
p
(
z
)
∈
Z
p.We use the same symbolφ
p to denote the homomorphism (13)
φ
p
:
Z
x
⟶
Z
p
x
,where Z
p
[
x
] is the ring of polynomials over Z
p and φ
p is mapping each of the coefficients a
i of f
(
x
)
∈
Z
[
x
] to the remainder after division of a
i by p.Similarly, we define the homomorphism of matrix rings(14)
φ
p
:
M
m
,
n
Z
⟶
M
m
,
n
Z
p
,which maps each of the elements a
i
j of a matrix A
∈
M
m
,
n
(
Z
) to the remainder after division of a
i
j by p.Using the same symbolφ
p for numeric, polynomial, and matrix homomorphisms causes no misunderstanding below, and it is more comfortable for some reasons. These homomorphisms are called“modular reductions” or just“reductions.” We can also specify these homomorphisms as“numeric modular reduction,” “polynomial modular reduction,” or“matrix modular reduction” where needed [1].Fora
∈
Z, denote φ
p
(
a
)
=
a
p. For f
(
x
)
∈
Z
[
x
], denote φ
p
(
f
(
x
)
)
=
f
p
(
x
)
∈
Z
p
[
x
]. So if(15)
f
x
=
a
0
x
n
+
⋯
+
a
nthen (16)
f
p
x
=
φ
p
f
x
=
φ
p
a
0
x
n
+
⋯
+
φ
p
a
n
=
a
0
,
p
x
n
+
⋯
+
a
n
,
p
∈
Z
p
x
.And for a matrix A
∈
M
m
,
n
(
Z
) denote φ
p
(
A
)
=
A
p
∈
M
m
,
n
(
Z
p
). If A
=
a
i
,
j
m
×
n, then A
p
=
φ
p
(
a
i
,
j
)
m
×
n
=
a
i
,
j
,
p
m
×
n.


## 4. Problems at Lifting the Modularg
c
d to Z
[
x
]

Now we turn to the second task mentioned earlier:effective calculation of the actual g
c
d
(
f
(
x
)
,
g
(
x
)
) for the given nonzero polynomials f
(
x
)
,
g
(
x
)
∈
Z
[
x
].The ringZ
p
[
x
] is an Euclidean domain, unlike the ring Z
[
x
]. So we can use the Euclidean algorithm to calculate g
c
d for any nonzero polynomials in Z
p
[
x
], including the modular images f
p
(
x
) and g
p
(
x
). Since the notation g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) is going to be used repeatedly, for briefness denote by e
p
(
x
)
g
c
d calculated by Euclidean algorithm for f
p
(
x
)
,
g
p
(
x
). Let us stress that g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) is not determined uniquely, since for any nonzero t
∈
Z
p the product t
·
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) also is g
c
d for f
p
(
x
)
,
g
p
(
x
). We are denoting justone of these g
c
d’s (namely, that computed by the Euclidean algorithm) by e
p
(
x
). This e
p
(
x
) is unique, since at each step of the Euclidean algorithm we have a unique action to take (to see this, just consider the steps of “long division” used to divide f
p
(
x
) by g
p
(
x
) on field Z
p).The main idea of the algorithm is to calculatee
p
(
x
)
≈
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) for some suitable p and to reconstruct d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
) by it. We separate the process to four main problems that may occur and show how to overcome each one to arrive to a correctly working algorithm.


### 4.1. Problem 1: Avoiding the Eliminating Coefficients

After reductionφ
p, some of the coefficients of f
(
x
) and g
(
x
) may change or even be eliminated. So their images f
p
(
x
)
=
φ
p
(
f
(
x
)
) and g
p
(
x
)
=
φ
p
(
g
(
x
)
) may keep very little information to reconstruct d
(
x
) based on e
p
(
x
).Example 5.
Iff
(
x
)
=
7
x
2
+
22 and g
(
x
)
=
49
x
3
+
154
x, then for p
=
7 we get f
p
(
x
)
=
1 and g
p
(
x
)
=
0. So these values contain no reliable information to reconstruct g
c
d
(
f
(
x
)
,
g
(
x
)
).The first simple idea to avoid such elimination is to takep larger than the absolute value of all coefficients of f
(
x
) and g
(
x
). This, however, is not enough since a divisor h
(
x
) of a polynomial f
(
x
) may have coefficients, larger than those of f
(
x
). Moreover, using the cyclotomic polynomials for large enough n, (17)
ϕ
n
x
=
∏
k
=
1
,
…
,
n
;
k
,
n
=
1
x
-
e
2
i
π
k
/
n
,one can get divisors of f
(
x
)
=
x
n
-
1 which have a coefficient larger than any pregiven number [1, 4, 8]. Since we do not know the divisors of f
(
x
) and g
(
x
), we cannot be sure if the abovementioned large p will be large enough to prevent elimination of coefficients of h
(
x
). To overcome this, one can use the Landau-Mignotte bounds (in different sources, the bounds on coefficients of the divisors are called differently, associating them with names of L. Landau or M. Mignotte or with both of them; these authors have different roles in development of the formulas, which in turn are consequence of a formula by A. L. Cauchy), as done in [4–6]. For a polynomial f
(
x
) given by (15), denote its norm by f
(
x
)
=
∑
i
=
0
n
a
i
2.Theorem 6 (L. Landau, M. Mignotte).
Letf
(
x
)
=
a
0
x
n
+
⋯
+
a
n and h
(
x
)
=
c
0
x
k
+
⋯
+
c
k be nonzero polynomials in Z
[
x
]. If h
(
x
) is a divisor of f
(
x
), then(18)
∑
i
=
0
n
c
i
≤
2
k
·
c
0
a
0
·
f
x
.The proof is based on calculations on complex numbers, and it can be found, for example, in [1, 4]. We are going to use the Landau-Mignotte bounds in the following two shapes.Corollary 7.
In notations of Theorem6, there is the following upper bound for the coefficients of h
(
x
):(19)
c
i
≤
N
f
=
2
n
-
1
f
x
.Proof.
To obtain this from (18), first notice that |
c
0
/
a
0
|
≤
1.
Next, ifk
=
deg
⁡
h
(
x
)
=
deg
⁡
f
(
x
)
=
n, then f
(
x
)
=
r
·
h
(
x
), where r is a nonzero integer. Then c
i
≤
max
⁡
c
i
∣
i
=
0
,
…
,
n
≤
max
⁡
|
a
i
|
∣
i
=
0
,
…
,
n
≤
f
(
x
).
Finally, ifk
=
deg
⁡
h
(
x
)
≤
n
-
1 (k is unknown to us), then we can simply replace in (18) the value 2
k by 2
n
-
1.Remark 8.
In literature, they use the rather less accurate bound|
c
i
|
≤
2
n
f
(
x
), but the second paragraph of our proof above allows replacing 2
n by 2
n
-
1. See also Remark 23.Corollary 9.
In notations of Theorem6, if h
(
x
) also is a divisor of the polynomial g
(
x
)
=
b
0
x
m
+
⋯
+
b
m, then there is the following upper bound for the coefficients of h
(
x
):(20)
c
i
≤
N
f
,
g
=
2
min
⁡
n
,
m
·
g
c
d
a
0
,
b
0
·
min
⁡
f
x
a
0
,
g
x
b
0
.Proof.
To obtain this from (18), just notice that if h
(
x
) is a common divisor for f
(
x
) and g
(
x
), then its leading coefficient c
0 divides both a
0 and b
0.Formula (20) provides the hint to overcome Problem 1 about eliminating coefficients, mentioned at the start of this subsection. Although the divisors h
(
x
) of f
(
x
) and g
(
x
) are yet unknown, we can compute N
f
,
g and take p
>
N
f
,
g. If we apply the reduction φ
p for this p, we can be sure that none of the coefficients of h
(
x
) has changed “much” under that homomorphism, for φ
p does not alter the nonnegative coefficients of h
(
x
), and it just adds p to all negative coefficients of h
(
x
). The same holds true for d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
).


### 4.2. Problem 2: Negative Coefficients and Reconstruction of the Preimage

The reductionφ
p is not a bijection, and d
p
(
x
) has infinitely many preimages in Z
[
x
]. But the relatively uncomplicated relationship between coefficients of d
(
x
) and d
p
(
x
), obtained in previous subsection, may allow us to reconstruct d
(
x
) if we know d
p
(
x
). The condition p
>
N
f
,
g puts a restriction on the preimage d
(
x
): the coefficients of d
(
x
) either are equal to respective coefficients of d
p
(
x
) (if they are nonnegative) or are the respective coefficients of d
p
(
x
) minus p (if they are negative). Reconstruction may cause problems connected with negative coefficients.Example 10.
If for some polynomialsf
(
x
)
,
g
(
x
) we have N
f
,
g
=
15, we can take the prime, say p
=
17
>
N
f
,
g. Assume we have somehow calculated d
17
(
x
)
=
12
x
3
+
3
x
+
10; we can be sure that d
(
x
) is not the preimage 29
x
3
-
17
x
2
+
20
x
+
27 because d
(
x
) cannot have coefficients greater than 15 by absolute value. But we still cannot be sure if the preimage d
(
x
) is 12
x
3
+
3
x
+
10, or -
5
x
3
+
3
x
+
10, or maybe -
5
x
3
-
14
x
-
7.It is easy to overcome this by just taking a larger value:(21)
p
>
2
·
N
f
,
g
.If the coefficient c
i of d
(
x
) is nonnegative, then φ
p
(
c
i
)
=
c
i
<
p
/
2, and if it is negative, then φ
p
(
c
i
)
=
c
i
+
p
>
p
/
2. This provides us with the very simple method as shown in Algorithm 1 to reconstruct d
(
x
) if we have already computed d
p
(
x
) for sufficiently large prime p.Algorithm 1:The polynomial reconstruction by modular image.
Input: For an unknown polynomial
d
(
x
)
∈
Z
[
x
]
we know
the upper bound
N
of absolute values of its coefficients,
and for arbitrarily large prime number
p
we have the
modular image
d
p
(
x
)
=
b
0
,
p
x
k
+
⋯
+
b
k
,
p
∈
Z
p
[
x
]
.
Reconstruct the polynomial
d
(
x
)
.
(01) Choose any primep
>
2
⋅
N.
(02) Setk
=
deg
⁡
d
p
(
x
).
(03) Seti
=
0.
(04) Whilei
≤
k
(05)  ifb
i
,
p
<
p
/
2
(06)    setb
i
=
b
i
,
p;
(07)  else
(08)    setb
i
=
b
i
,
p
-
p;
(10)  seti
=
i
+
1.
(11) Outputd
(
x
)
=
b
0
x
k
+
⋯
+
b
k.Algorithm 2:Big prime modular gcd algorithm.
Input: non-zero polynomials
f
(
x
)
,
g
(
x
)
∈
Z
[
x
].
Calculate their greatest common divisor  gcd(
f
(
x
)
,
g
(
x
)
)
∈
Z
[
x
].
(01) Calculate contf
(
x
), contg
(
x
) in the Euclidean domain Z, choose their signs so that sgn
⁡
c
o
n
t
f
(
x
)
=
sgn
⁡
lc
⁡
f
(
x
)
andsgn
⁡
cont
⁡
g
(
x
)
=
sgn
⁡
l
c
g
(
x
).
(02) Setf
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
).
(03) Calculater in the Euclidean domain Z by (25).
(04) Seta
0
=
l
c
f
(
x
) and b
0
=
l
c
g
(
x
) (they are positive by our selection of signs for c
o
n
t
f
(
x
) and c
o
n
t
g
(
x
)).
(05) Calculate the positivew
=
g
c
d
(
a
0
,
b
0
) in the Euclidean domain Z.
(06) SetD
=
min
⁡
deg
⁡
f
x
,
deg
⁡
g
x
+
1.
(07) Compute the Landau-Mignotte boundN
f
,
g by (20).
(08) Choose a new prime numberp
>
2
⋅
N
f
,
g.
(09) Apply the reductionφ
p to calculate the modular images f
p
(
x
)
,
g
p
(
x
)
∈
Z
p
[
x
].
(10) Calculatee
p
(
x
)
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) in the Euclidean domain Z
p
[
x
].
(11) IfD
≤
deg
⁡
e
p
(
x
)
(12)  go to step (08);
(13) else
(14)  choose at such that the l
c
t
⋅
e
p
(
x
)
=
w;
(15)  call Algorithm1 to calculate the preimage k
(
x
) of t
⋅
e
p
(
x
);
(16)  calculatec
o
n
t
k
(
x
) in the Euclidean domain Z;
(17)  setd
(
x
)
=
p
p
k
(
x
)
=
k
(
x
)
/
c
o
n
t
k
(
x
);
(18)    ifd
x
∣
f
(
x
) and d
x
∣
g
(
x
)
(19)      go to step (23);
(20)    else
(21)      setD
=
deg
⁡
e
p
(
x
);
(22)      go to step (08).
(23)  Output the result:g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
r
⋅
d
(
x
).Algorithm 3:Coprime polynomials detection modular algorithm.
Input: non-zero polynomials
f
(
x
)
,
g
(
x
)
∈
Z
[
x
].
Detect if
f
(
x
)
and
g
(
x
)
are coprime.
(01) Calculatec
o
n
t
f
(
x
), c
o
n
t
g
(
x
) in the Euclidean domain Z.
(02) Calculater in the Euclidean domain Z by (25).
(03) Ifr
≉
1
(04)  output the result:f
(
x
) and g
(
x
) are not coprime and stop.
(05) Seta
0
=
l
c
f
(
x
) and b
0
=
l
c
g
(
x
).
(06) Calculatew
=
g
c
d
(
a
0
,
b
0
) in the Euclidean domain Z.
(07) Setf
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
).
(08) Compute the boundA
f
,
g for polynomials f
(
x
)
,
g
(
x
) by (32).
(09) Find the maximalk for which p
k
#
≤
A
f
,
g.
(10)  Seti
=
1.
(11)  Whilei
≠
k
+
1
(12)  choose a new primep
∤
w;
(13)  apply the reductionφ
p to calculate the modular images f
p
(
x
)
,
g
p
(
x
)
∈
Z
p
[
x
];
(14)  calculatee
p
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) in the Euclidean domain Z
p
[
x
];
(15)    ifdeg
⁡
e
q
i
=
0
(16)      output the result:f
(
x
) and g
(
x
) are coprime and stop.
(17)  seti
=
i
+
1.
(18)  Ifi
<
k
+
1
(19)  go to step (12).
(20)  else
(21)  output the result:f
(
x
) and g
(
x
) are not coprime.Algorithm 4:Big prime modular gcd algorithm with a preliminary estimate on divisor degree.
Input: non-zero polynomials
f
(
x
)
,
g
(
x
)
∈
Z
[
x
].
Calculate their greatest common divisor  g
c
d
(
f
(
x
)
,
g
(
x
)
)
∈
Z
[
x
].
(01) Calculatec
o
n
t
f
(
x
), c
o
n
t
g
(
x
) in the Euclidean domain Z, choose their signs
so thats
g
n
c
o
n
t
f
(
x
)
=
sgn
⁡
l
c
f
(
x
) and sgn
⁡
c
o
n
t
g
(
x
)
=
sgn
⁡
l
c
g
(
x
).
(02) Setf
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
).
(03) Calculater in the Euclidean domain Z by (25).
(04) Seta
0
=
l
c
f
(
x
) and b
0
=
l
c
g
(
x
) (they are positive by our selection of signs
forc
o
n
t
f
(
x
) and c
o
n
t
g
(
x
)).
(05) Calculate the positivew
=
g
c
d
(
a
0
,
b
0
) in the Euclidean domain Z.
(06) SetD
=
min
⁡
deg
⁡
f
x
,
deg
⁡
g
x
+
1.
(07) Choose a prime numberq
∤
w.
(08) Apply the reductionφ
q to calculate the modular images f
q
(
x
)
,
g
q
(
x
)
∈
Z
q
[
x
].
(09) Calculatee
q
(
x
)
=
g
c
d
(
f
q
(
x
)
,
g
q
(
x
)
) in the Euclidean domain Z
q
[
x
].
(10) Sets
(
q
,
f
,
g
)
=
deg
⁡
e
q
(
x
).
(11) CalculateM
q
,
f
,
g by (40) using the value of s
(
q
,
f
,
g
).
(12) Choose a new prime numberp
>
2
⋅
M
q
,
f
,
g.
(13) Apply the reductionφ
p to calculate the modular images f
p
(
x
)
,
g
p
(
x
)
∈
Z
p
[
x
].
(14) Calculatee
p
(
x
)
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) in the Euclidean domain Z
p
[
x
].
(15) IfD
≤
deg
⁡
e
p
(
x
)
(16)  go to step (12).
(17) else
(18)  choose at such that the l
c
t
⋅
e
p
(
x
)
=
w;
(19)  call Algorithm1 to calculate the preimage k
(
x
) of t
⋅
e
p
(
x
);
(20)  calculatec
o
n
t
k
(
x
) in the Euclidean domain Z;
(21)  setd
(
x
)
=
p
p
k
x
=
k
(
x
)
/
cont
⁡
k
(
x
);
(22)    ifd
x
∣
f
(
x
) and d
x
∣
g
(
x
)
(23)      go to step (27);
(24)     else
(25)      setD
=
deg
⁡
e
p
(
x
);
(26)      go to step (12).
(27) Output the result:g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
r
⋅
d
(
x
).Algorithm 5:Big prime modular gcd algorithm with preliminary estimates on divisor degrees by multiple primes.
Input: non-zero polynomials
f
(
x
)
,
g
(
x
)
∈
Z
[
x
].
Calculate their greatest common divisor  g
c
d
(
f
(
x
)
,
g
(
x
)
)
∈
Z
[
x
].
(01) Calculatec
o
n
t
f
(
x
), c
o
n
t
g
(
x
) in the Euclidean domain Z, choose their signs
so thatsgn
⁡
cont
⁡
f
(
x
)
=
sgn
⁡
lc
⁡
f
(
x
) and sgn
⁡
cont
⁡
g
(
x
)
=
sgn
⁡
lc
⁡
g
(
x
).
(02) Setf
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
).
(03) Compute the boundA
f
,
g for polynomials f
(
x
)
,
g
(
x
) by (32).
(04) Find the maximalk for which p
k
#
≤
A
f
,
g.
(05) Calculater in the Euclidean domain Z by (25).
(06) Seta
0
=
l
c
f
(
x
) and b
0
=
l
c
g
(
x
) (they are positive by our selection of signs
forc
o
n
t
f
(
x
) and c
o
n
t
g
(
x
)).
(07) Calculate the positivew
=
g
c
d
(
a
0
,
b
0
) in the Euclidean domain Z.
(08) Sets
f
,
g
=
min
⁡
deg
⁡
f
x
,
deg
⁡
g
x.
(09) Seti
=
1.
(10) Whilei
≠
k
+
1
(11)  choose a new primeq
i
∤
w;
(12)  apply the reductionφ
q
i to calculate the modular images f
q
i
(
x
)
,
g
q
i
(
x
)
∈
Z
q
i
[
x
];
(13)  calculatee
q
i
=
g
c
d
(
f
q
i
(
x
)
,
g
q
i
(
x
)
) in the Euclidean domain Z
p
[
x
];
(14)  ifdeg
⁡
e
q
i
≤
s
(
f
,
g
)
(15)    sets
(
f
,
g
)
=
deg
⁡
e
q
i;
(16)    ifdeg
⁡
e
q
i
=
0
(17)      setd
(
x
)
=
1;
(18)      go to step (32);
(19)  seti
=
i
+
1.
(20) CalculateM
f
,
g by (43) using the value of s
(
f
,
g
).
(21) Choose a new prime numberp
>
2
⋅
M
f
,
g.
(22) Apply the reductionφ
p to calculate the modular images f
p
(
x
)
,
g
p
(
x
)
∈
Z
p
[
x
].
(23) Calculatee
p
(
x
)
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) in the Euclidean domain Z
p
[
x
].
(24) Ifdeg
⁡
e
p
=
s
(
f
,
g
)
(25)  choose at such that the l
c
t
⋅
e
p
(
x
)
=
w;
(26)  call Algorithm1 to calculate the preimage k
(
x
) of t
⋅
e
p
(
x
);
(27)  calculatec
o
n
t
k
(
x
) in the Euclidean domain Z;
(28)  setd
(
x
)
=
p
p
k
(
x
)
=
k
(
x
)
/
c
o
n
t
k
(
x
);
(29)  go to step (32);
(30) else
(31)  go to step (21).
(32) Output the result:g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
r
⋅
d
(
x
).


### 4.3. Problem 3: Finding the Correct Fold of the Modularg
c
d of Right Degree

Now additionally assume the polynomialsf
(
x
)
,
g
(
x
)
∈
Z
[
x
] to be primitive. Since c
o
n
t
f
(
x
) and c
o
n
t
g
(
x
) are defined up to the sign ±
1, we can without loss of generality admit the leading coefficients of f
(
x
)
,
g
(
x
) to be positive.Below, in Problem 4, we will see that for somep the polynomial e
p
(
x
), computed by the Euclidean algorithm in Z
p
[
x
], may not be the image of d
(
x
) and, moreover, its degree may be different from that of d
(
x
). This means that by applying Algorithm 1 to e
p
(
x
) we may not obtain d
(
x
). Assume, however, we have p, which meets the condition p
>
2
·
N
f
,
g and for which(22)
deg
⁡
d
x
=
deg
⁡
e
p
x
.By Corollary 3, a common divisor of f
(
x
)
,
g
(
x
) is d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
) if and only if it is primitive and if its degree is the maximum of degrees of all common divisors. Since φ
p does not change the degree of d
(
x
), we get by Lemma 4 (applied for the field K
=
Z
p) that d
p
(
x
) is g
c
d of f
p
(
x
)
,
g
p
(
x
) in Z
p
[
x
]. This correspondence surely is not one-to-one, because in Z
[
x
]
g
c
d is calculated up to the unit element of Z
[
x
], which is ±
1, whereas in Z
p
[
x
]
g
c
d is calculated up to the unit element of Z
p
[
x
], which can be any nonzero number t
∈
Z
p
∗
=
{
1
,
…
,
p
-
1
}. So the polynomial e
p
(
x
) calculated by the Euclidean algorithm may not be the image d
p
(
x
) of d
(
x
).Example 11.
Forf
(
x
)
=
x
2
+
4
x
+
3 and g
(
x
)
=
x
2
+
2
x
+
1, whichever prime p
>
4 we take, we will get by the Euclidean algorithm (23)
e
p
x
=
g
c
d
f
p
x
,
g
p
x
=
2
x
+
2
∈
Z
p
x
.But in Z
[
x
] we have d
(
x
)
=
x
+
1. So regardless how large p we choose, we will never get φ
p
(
x
+
1
)
=
2
x
+
2.In other words, we are aware that the imaged
p
(
x
) is one of the folds t
·
e
p
(
x
) of e
p
(
x
) for some t
∈
{
1
,
…
,
p
-
1
}, but we are not aware which t is that.The leading coefficientc
0
=
l
c
d
(
x
) of d
(
x
) can also be assumed to be positive. Denote by w the positive g
c
d
(
a
0
,
b
0
). Since both c
0 and w are not altered by φ
p, their fraction w
/
c
0 also is not altered. Take such t that(24)
l
c
t
·
e
p
x
=
w
.Even if t
·
e
p
(
x
) is not the image d
p
(
x
), it is the image of l
·
d
(
x
), where l divides w
/
c
0. If we calculate the preimage k
(
x
)
∈
Z
[
x
] of t
·
e
p
(
x
) by Algorithm 1, we will get a polynomial, which is either d
(
x
) or some fold of d
(
x
). Since f
(
x
)
,
g
(
x
) are primitive, it remains to go to the primitive part d
(
x
)
=
p
p
k
(
x
).The general case, whenf
(
x
)
,
g
(
x
) may not be primitive, can easily be reduced to the following: for arbitrary f
(
x
)
,
g
(
x
), take their decompositions by formula (5) and set(25)
r
=
g
c
d
c
o
n
t
f
x
,
c
o
n
t
g
x
∈
Z
.Then assign f
(
x
)
=
p
p
f
(
x
), g
(
x
)
=
p
p
g
(
x
) and do the steps above for these new polynomials. After d
(
x
)
=
p
p
k
(
x
) is computed, we get the final answer as r
·
d
(
x
)
=
r
·
p
p
k
(
x
).Notice that for Algorithm1 we need p to be greater than any coefficient |
c
i
| of the polynomial we reconstruct. The bound p
>
2
·
N
f
,
g assures that p meets this condition for d
(
x
). We, however, reconstruct not d
(
x
) but l
·
d
(
x
), which may have larger coefficients. One could overcome this point by taking p
>
w
·
2
·
N
f
,
g, but this is not necessary because as we see later, while the Big prime modular g
c
d algorithm works, the value of p will grow and this issue will be covered.


### 4.4. Problem 4: Finding the Right Degree for the Modularg
c
d

As we saw, one can reconstructd
(
x
) if we find p
>
2
·
N
f
,
g such that condition (22) holds. Consider an example to see that (22) may actually not hold for some p even if φ
p is not altering the coefficients of f
(
x
) and g
(
x
)!Example 12.
Forf
(
x
)
=
x
2
+
1 and g
(
x
)
=
x
+
1, we have d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
1. Taking p
=
2 we get f
2
(
x
)
=
x
2
+
1 and g
2
(
x
)
=
x
+
1. In Z
2
[
x
] we have f
2
(
x
)
=
x
2
+
1
=
x
2
+
1
2
=
(
x
+
1
)
(
x
+
1
); thus, e
2
(
x
)
=
g
c
d
(
f
2
(
x
)
,
g
2
(
x
)
)
=
x
+
1. We get that 1
=
deg
⁡
(
x
+
1
)
>
deg
⁡
x
=
0. In particular, whatever t we take, t
·
(
x
+
1
) is not the image of d
(
x
)
=
1 under φ
2.The idea to overcome this problem is to show that the number of primesp, for which (22) falsifies, is “small.” So if the selected p is not suitable, we take another p and do the calculation again by the new prime. And we will not have to repeat these steps for many times (we will turn to this point in Section 6).The proof of the following theorem and the definition of the resultantr
e
s
(
f
(
x
)
,
g
(
x
)
) (i.e., of the determinant of the Sylvester matrix S
f
,
g of polynomials f
(
x
)
,
g
(
x
)) can be found, for example, in [1, 4, 7, 10]. The resultant is a comfortable tool to detect if the given polynomials are coprime.Theorem 13.
LetR be an integrity domain. The polynomials f
(
x
)
,
g
(
x
)
∈
R
[
x
] are coprime if and only if r
e
s
(
f
(
x
)
,
g
(
x
)
)
≠
0.The following fact in a little different shape can be found in [4] or [5].Corollary 14.
If the primep does not divide at least one of the leading coefficients a
0, b
0 of polynomials, respectively, f
(
x
)
,
g
(
x
)
∈
Z
[
x
], then deg
⁡
d
(
x
)
≤
deg
⁡
e
p
(
x
). If p also does not divide R
=
r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
), where d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
), then(26)
deg
⁡
d
x
=
deg
⁡
d
p
x
=
deg
⁡
g
c
d
f
p
x
,
g
p
x
=
deg
⁡
e
p
x
.Proof.
Sincec
0
=
l
c
d
(
x
) divides w
=
g
c
d
(
a
0
,
b
0
), then φ
p
(
c
0
)
≠
0 by the choice of p. Thus, deg
⁡
d
(
x
)
=
deg
⁡
d
p
(
x
)
≤
deg
⁡
g
c
d
f
p
x
,
g
p
x.
Sinced
p
(
x
)
≠
0, we can consider the fractions f
p
(
x
)
/
d
p
(
x
) and g
p
(
x
)
/
d
p
(
x
) in Z
p
[
x
]. From unique factorizations of f
p
(
x
) and g
p
(
x
) in UFD Z
p
[
x
], it is very easy to deduce that (27)
e
p
x
≈
g
c
d
f
p
x
,
g
p
x
≈
d
p
x
·
g
c
d
f
p
x
d
p
x
,
g
p
x
d
p
x
.In particular, deg
⁡
d
(
x
)
=
deg
⁡
d
p
(
x
)
≤
deg
⁡
e
p
(
x
). And the inequality deg
⁡
d
p
(
x
)
≠
deg
⁡
e
p
(
x
) may occur only if (28)
deg
⁡
g
c
d
f
p
x
d
p
x
,
g
p
x
d
p
x
>
0
,that is, when f
p
(
x
)
/
d
p
(
x
) and g
p
(
x
)
/
d
p
(
x
) are not coprime in Z
p
[
x
] or, by Theorem 13, when r
e
s
(
f
p
(
x
)
/
d
p
(
x
)
,
g
p
(
x
)
/
d
p
(
x
)
)
=
0. The latter is the determinant of Sylvester matrix S
f
p
/
d
p
,
g
p
/
d
p. Consider the matrix rings homomorphism (matrix modular reduction) (29)
φ
p
:
M
m
+
n
Z
⟶
M
m
+
n
Z
p
,where n
=
deg
⁡
f
(
x
); m
=
deg
⁡
g
(
x
) (as mentioned earlier we use the same symbol φ
p for numeric, polynomial, and matrix reductions). Since, φ
p
(
S
f
/
d
,
g
/
d
)
=
S
f
p
/
d
p
,
g
p
/
d
p and since the determinant of a matrix is a sum of products of its elements, we get (30)
R
p
=
φ
p
R
=
φ
p
r
e
s
f
x
d
x
,
g
x
d
x
=
r
e
s
f
p
x
d
p
x
,
g
p
x
d
p
x
.So R
p can be zero if and only if R is divisible by p. The polynomials f
(
x
)
/
d
(
x
) and g
(
x
)
/
d
(
x
) are coprime in Z
[
x
] and their resultant is not zero by Theorem 13. And R cannot be a positive integer divisible by p since that contradicts the condition of this corollary.Corollary14 shows that if for some p equality (22) does not hold for polynomials f
(
x
)
,
g
(
x
)
∈
Z
[
x
], then p either divides a
0 and b
0 or divides the resultant R. We do not know R, since we do not yet know d
(
x
) to calculate the resultant R
=
r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
). But since the number of such primes p is just finite, we can arrive to the right p after trying the process for a few primes. We will turn to this again in Section 6.


## 4.1. Problem 1: Avoiding the Eliminating Coefficients

After reductionφ
p, some of the coefficients of f
(
x
) and g
(
x
) may change or even be eliminated. So their images f
p
(
x
)
=
φ
p
(
f
(
x
)
) and g
p
(
x
)
=
φ
p
(
g
(
x
)
) may keep very little information to reconstruct d
(
x
) based on e
p
(
x
).Example 5.
Iff
(
x
)
=
7
x
2
+
22 and g
(
x
)
=
49
x
3
+
154
x, then for p
=
7 we get f
p
(
x
)
=
1 and g
p
(
x
)
=
0. So these values contain no reliable information to reconstruct g
c
d
(
f
(
x
)
,
g
(
x
)
).The first simple idea to avoid such elimination is to takep larger than the absolute value of all coefficients of f
(
x
) and g
(
x
). This, however, is not enough since a divisor h
(
x
) of a polynomial f
(
x
) may have coefficients, larger than those of f
(
x
). Moreover, using the cyclotomic polynomials for large enough n, (17)
ϕ
n
x
=
∏
k
=
1
,
…
,
n
;
k
,
n
=
1
x
-
e
2
i
π
k
/
n
,one can get divisors of f
(
x
)
=
x
n
-
1 which have a coefficient larger than any pregiven number [1, 4, 8]. Since we do not know the divisors of f
(
x
) and g
(
x
), we cannot be sure if the abovementioned large p will be large enough to prevent elimination of coefficients of h
(
x
). To overcome this, one can use the Landau-Mignotte bounds (in different sources, the bounds on coefficients of the divisors are called differently, associating them with names of L. Landau or M. Mignotte or with both of them; these authors have different roles in development of the formulas, which in turn are consequence of a formula by A. L. Cauchy), as done in [4–6]. For a polynomial f
(
x
) given by (15), denote its norm by f
(
x
)
=
∑
i
=
0
n
a
i
2.Theorem 6 (L. Landau, M. Mignotte).
Letf
(
x
)
=
a
0
x
n
+
⋯
+
a
n and h
(
x
)
=
c
0
x
k
+
⋯
+
c
k be nonzero polynomials in Z
[
x
]. If h
(
x
) is a divisor of f
(
x
), then(18)
∑
i
=
0
n
c
i
≤
2
k
·
c
0
a
0
·
f
x
.The proof is based on calculations on complex numbers, and it can be found, for example, in [1, 4]. We are going to use the Landau-Mignotte bounds in the following two shapes.Corollary 7.
In notations of Theorem6, there is the following upper bound for the coefficients of h
(
x
):(19)
c
i
≤
N
f
=
2
n
-
1
f
x
.Proof.
To obtain this from (18), first notice that |
c
0
/
a
0
|
≤
1.
Next, ifk
=
deg
⁡
h
(
x
)
=
deg
⁡
f
(
x
)
=
n, then f
(
x
)
=
r
·
h
(
x
), where r is a nonzero integer. Then c
i
≤
max
⁡
c
i
∣
i
=
0
,
…
,
n
≤
max
⁡
|
a
i
|
∣
i
=
0
,
…
,
n
≤
f
(
x
).
Finally, ifk
=
deg
⁡
h
(
x
)
≤
n
-
1 (k is unknown to us), then we can simply replace in (18) the value 2
k by 2
n
-
1.Remark 8.
In literature, they use the rather less accurate bound|
c
i
|
≤
2
n
f
(
x
), but the second paragraph of our proof above allows replacing 2
n by 2
n
-
1. See also Remark 23.Corollary 9.
In notations of Theorem6, if h
(
x
) also is a divisor of the polynomial g
(
x
)
=
b
0
x
m
+
⋯
+
b
m, then there is the following upper bound for the coefficients of h
(
x
):(20)
c
i
≤
N
f
,
g
=
2
min
⁡
n
,
m
·
g
c
d
a
0
,
b
0
·
min
⁡
f
x
a
0
,
g
x
b
0
.Proof.
To obtain this from (18), just notice that if h
(
x
) is a common divisor for f
(
x
) and g
(
x
), then its leading coefficient c
0 divides both a
0 and b
0.Formula (20) provides the hint to overcome Problem 1 about eliminating coefficients, mentioned at the start of this subsection. Although the divisors h
(
x
) of f
(
x
) and g
(
x
) are yet unknown, we can compute N
f
,
g and take p
>
N
f
,
g. If we apply the reduction φ
p for this p, we can be sure that none of the coefficients of h
(
x
) has changed “much” under that homomorphism, for φ
p does not alter the nonnegative coefficients of h
(
x
), and it just adds p to all negative coefficients of h
(
x
). The same holds true for d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
).


## 4.2. Problem 2: Negative Coefficients and Reconstruction of the Preimage

The reductionφ
p is not a bijection, and d
p
(
x
) has infinitely many preimages in Z
[
x
]. But the relatively uncomplicated relationship between coefficients of d
(
x
) and d
p
(
x
), obtained in previous subsection, may allow us to reconstruct d
(
x
) if we know d
p
(
x
). The condition p
>
N
f
,
g puts a restriction on the preimage d
(
x
): the coefficients of d
(
x
) either are equal to respective coefficients of d
p
(
x
) (if they are nonnegative) or are the respective coefficients of d
p
(
x
) minus p (if they are negative). Reconstruction may cause problems connected with negative coefficients.Example 10.
If for some polynomialsf
(
x
)
,
g
(
x
) we have N
f
,
g
=
15, we can take the prime, say p
=
17
>
N
f
,
g. Assume we have somehow calculated d
17
(
x
)
=
12
x
3
+
3
x
+
10; we can be sure that d
(
x
) is not the preimage 29
x
3
-
17
x
2
+
20
x
+
27 because d
(
x
) cannot have coefficients greater than 15 by absolute value. But we still cannot be sure if the preimage d
(
x
) is 12
x
3
+
3
x
+
10, or -
5
x
3
+
3
x
+
10, or maybe -
5
x
3
-
14
x
-
7.It is easy to overcome this by just taking a larger value:(21)
p
>
2
·
N
f
,
g
.If the coefficient c
i of d
(
x
) is nonnegative, then φ
p
(
c
i
)
=
c
i
<
p
/
2, and if it is negative, then φ
p
(
c
i
)
=
c
i
+
p
>
p
/
2. This provides us with the very simple method as shown in Algorithm 1 to reconstruct d
(
x
) if we have already computed d
p
(
x
) for sufficiently large prime p.Algorithm 1:The polynomial reconstruction by modular image.
Input: For an unknown polynomial
d
(
x
)
∈
Z
[
x
]
we know
the upper bound
N
of absolute values of its coefficients,
and for arbitrarily large prime number
p
we have the
modular image
d
p
(
x
)
=
b
0
,
p
x
k
+
⋯
+
b
k
,
p
∈
Z
p
[
x
]
.
Reconstruct the polynomial
d
(
x
)
.
(01) Choose any primep
>
2
⋅
N.
(02) Setk
=
deg
⁡
d
p
(
x
).
(03) Seti
=
0.
(04) Whilei
≤
k
(05)  ifb
i
,
p
<
p
/
2
(06)    setb
i
=
b
i
,
p;
(07)  else
(08)    setb
i
=
b
i
,
p
-
p;
(10)  seti
=
i
+
1.
(11) Outputd
(
x
)
=
b
0
x
k
+
⋯
+
b
k.Algorithm 2:Big prime modular gcd algorithm.
Input: non-zero polynomials
f
(
x
)
,
g
(
x
)
∈
Z
[
x
].
Calculate their greatest common divisor  gcd(
f
(
x
)
,
g
(
x
)
)
∈
Z
[
x
].
(01) Calculate contf
(
x
), contg
(
x
) in the Euclidean domain Z, choose their signs so that sgn
⁡
c
o
n
t
f
(
x
)
=
sgn
⁡
lc
⁡
f
(
x
)
andsgn
⁡
cont
⁡
g
(
x
)
=
sgn
⁡
l
c
g
(
x
).
(02) Setf
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
).
(03) Calculater in the Euclidean domain Z by (25).
(04) Seta
0
=
l
c
f
(
x
) and b
0
=
l
c
g
(
x
) (they are positive by our selection of signs for c
o
n
t
f
(
x
) and c
o
n
t
g
(
x
)).
(05) Calculate the positivew
=
g
c
d
(
a
0
,
b
0
) in the Euclidean domain Z.
(06) SetD
=
min
⁡
deg
⁡
f
x
,
deg
⁡
g
x
+
1.
(07) Compute the Landau-Mignotte boundN
f
,
g by (20).
(08) Choose a new prime numberp
>
2
⋅
N
f
,
g.
(09) Apply the reductionφ
p to calculate the modular images f
p
(
x
)
,
g
p
(
x
)
∈
Z
p
[
x
].
(10) Calculatee
p
(
x
)
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) in the Euclidean domain Z
p
[
x
].
(11) IfD
≤
deg
⁡
e
p
(
x
)
(12)  go to step (08);
(13) else
(14)  choose at such that the l
c
t
⋅
e
p
(
x
)
=
w;
(15)  call Algorithm1 to calculate the preimage k
(
x
) of t
⋅
e
p
(
x
);
(16)  calculatec
o
n
t
k
(
x
) in the Euclidean domain Z;
(17)  setd
(
x
)
=
p
p
k
(
x
)
=
k
(
x
)
/
c
o
n
t
k
(
x
);
(18)    ifd
x
∣
f
(
x
) and d
x
∣
g
(
x
)
(19)      go to step (23);
(20)    else
(21)      setD
=
deg
⁡
e
p
(
x
);
(22)      go to step (08).
(23)  Output the result:g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
r
⋅
d
(
x
).Algorithm 3:Coprime polynomials detection modular algorithm.
Input: non-zero polynomials
f
(
x
)
,
g
(
x
)
∈
Z
[
x
].
Detect if
f
(
x
)
and
g
(
x
)
are coprime.
(01) Calculatec
o
n
t
f
(
x
), c
o
n
t
g
(
x
) in the Euclidean domain Z.
(02) Calculater in the Euclidean domain Z by (25).
(03) Ifr
≉
1
(04)  output the result:f
(
x
) and g
(
x
) are not coprime and stop.
(05) Seta
0
=
l
c
f
(
x
) and b
0
=
l
c
g
(
x
).
(06) Calculatew
=
g
c
d
(
a
0
,
b
0
) in the Euclidean domain Z.
(07) Setf
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
).
(08) Compute the boundA
f
,
g for polynomials f
(
x
)
,
g
(
x
) by (32).
(09) Find the maximalk for which p
k
#
≤
A
f
,
g.
(10)  Seti
=
1.
(11)  Whilei
≠
k
+
1
(12)  choose a new primep
∤
w;
(13)  apply the reductionφ
p to calculate the modular images f
p
(
x
)
,
g
p
(
x
)
∈
Z
p
[
x
];
(14)  calculatee
p
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) in the Euclidean domain Z
p
[
x
];
(15)    ifdeg
⁡
e
q
i
=
0
(16)      output the result:f
(
x
) and g
(
x
) are coprime and stop.
(17)  seti
=
i
+
1.
(18)  Ifi
<
k
+
1
(19)  go to step (12).
(20)  else
(21)  output the result:f
(
x
) and g
(
x
) are not coprime.Algorithm 4:Big prime modular gcd algorithm with a preliminary estimate on divisor degree.
Input: non-zero polynomials
f
(
x
)
,
g
(
x
)
∈
Z
[
x
].
Calculate their greatest common divisor  g
c
d
(
f
(
x
)
,
g
(
x
)
)
∈
Z
[
x
].
(01) Calculatec
o
n
t
f
(
x
), c
o
n
t
g
(
x
) in the Euclidean domain Z, choose their signs
so thats
g
n
c
o
n
t
f
(
x
)
=
sgn
⁡
l
c
f
(
x
) and sgn
⁡
c
o
n
t
g
(
x
)
=
sgn
⁡
l
c
g
(
x
).
(02) Setf
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
).
(03) Calculater in the Euclidean domain Z by (25).
(04) Seta
0
=
l
c
f
(
x
) and b
0
=
l
c
g
(
x
) (they are positive by our selection of signs
forc
o
n
t
f
(
x
) and c
o
n
t
g
(
x
)).
(05) Calculate the positivew
=
g
c
d
(
a
0
,
b
0
) in the Euclidean domain Z.
(06) SetD
=
min
⁡
deg
⁡
f
x
,
deg
⁡
g
x
+
1.
(07) Choose a prime numberq
∤
w.
(08) Apply the reductionφ
q to calculate the modular images f
q
(
x
)
,
g
q
(
x
)
∈
Z
q
[
x
].
(09) Calculatee
q
(
x
)
=
g
c
d
(
f
q
(
x
)
,
g
q
(
x
)
) in the Euclidean domain Z
q
[
x
].
(10) Sets
(
q
,
f
,
g
)
=
deg
⁡
e
q
(
x
).
(11) CalculateM
q
,
f
,
g by (40) using the value of s
(
q
,
f
,
g
).
(12) Choose a new prime numberp
>
2
⋅
M
q
,
f
,
g.
(13) Apply the reductionφ
p to calculate the modular images f
p
(
x
)
,
g
p
(
x
)
∈
Z
p
[
x
].
(14) Calculatee
p
(
x
)
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) in the Euclidean domain Z
p
[
x
].
(15) IfD
≤
deg
⁡
e
p
(
x
)
(16)  go to step (12).
(17) else
(18)  choose at such that the l
c
t
⋅
e
p
(
x
)
=
w;
(19)  call Algorithm1 to calculate the preimage k
(
x
) of t
⋅
e
p
(
x
);
(20)  calculatec
o
n
t
k
(
x
) in the Euclidean domain Z;
(21)  setd
(
x
)
=
p
p
k
x
=
k
(
x
)
/
cont
⁡
k
(
x
);
(22)    ifd
x
∣
f
(
x
) and d
x
∣
g
(
x
)
(23)      go to step (27);
(24)     else
(25)      setD
=
deg
⁡
e
p
(
x
);
(26)      go to step (12).
(27) Output the result:g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
r
⋅
d
(
x
).Algorithm 5:Big prime modular gcd algorithm with preliminary estimates on divisor degrees by multiple primes.
Input: non-zero polynomials
f
(
x
)
,
g
(
x
)
∈
Z
[
x
].
Calculate their greatest common divisor  g
c
d
(
f
(
x
)
,
g
(
x
)
)
∈
Z
[
x
].
(01) Calculatec
o
n
t
f
(
x
), c
o
n
t
g
(
x
) in the Euclidean domain Z, choose their signs
so thatsgn
⁡
cont
⁡
f
(
x
)
=
sgn
⁡
lc
⁡
f
(
x
) and sgn
⁡
cont
⁡
g
(
x
)
=
sgn
⁡
lc
⁡
g
(
x
).
(02) Setf
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
).
(03) Compute the boundA
f
,
g for polynomials f
(
x
)
,
g
(
x
) by (32).
(04) Find the maximalk for which p
k
#
≤
A
f
,
g.
(05) Calculater in the Euclidean domain Z by (25).
(06) Seta
0
=
l
c
f
(
x
) and b
0
=
l
c
g
(
x
) (they are positive by our selection of signs
forc
o
n
t
f
(
x
) and c
o
n
t
g
(
x
)).
(07) Calculate the positivew
=
g
c
d
(
a
0
,
b
0
) in the Euclidean domain Z.
(08) Sets
f
,
g
=
min
⁡
deg
⁡
f
x
,
deg
⁡
g
x.
(09) Seti
=
1.
(10) Whilei
≠
k
+
1
(11)  choose a new primeq
i
∤
w;
(12)  apply the reductionφ
q
i to calculate the modular images f
q
i
(
x
)
,
g
q
i
(
x
)
∈
Z
q
i
[
x
];
(13)  calculatee
q
i
=
g
c
d
(
f
q
i
(
x
)
,
g
q
i
(
x
)
) in the Euclidean domain Z
p
[
x
];
(14)  ifdeg
⁡
e
q
i
≤
s
(
f
,
g
)
(15)    sets
(
f
,
g
)
=
deg
⁡
e
q
i;
(16)    ifdeg
⁡
e
q
i
=
0
(17)      setd
(
x
)
=
1;
(18)      go to step (32);
(19)  seti
=
i
+
1.
(20) CalculateM
f
,
g by (43) using the value of s
(
f
,
g
).
(21) Choose a new prime numberp
>
2
⋅
M
f
,
g.
(22) Apply the reductionφ
p to calculate the modular images f
p
(
x
)
,
g
p
(
x
)
∈
Z
p
[
x
].
(23) Calculatee
p
(
x
)
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) in the Euclidean domain Z
p
[
x
].
(24) Ifdeg
⁡
e
p
=
s
(
f
,
g
)
(25)  choose at such that the l
c
t
⋅
e
p
(
x
)
=
w;
(26)  call Algorithm1 to calculate the preimage k
(
x
) of t
⋅
e
p
(
x
);
(27)  calculatec
o
n
t
k
(
x
) in the Euclidean domain Z;
(28)  setd
(
x
)
=
p
p
k
(
x
)
=
k
(
x
)
/
c
o
n
t
k
(
x
);
(29)  go to step (32);
(30) else
(31)  go to step (21).
(32) Output the result:g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
r
⋅
d
(
x
).


## 4.3. Problem 3: Finding the Correct Fold of the Modularg
c
d of Right Degree

Now additionally assume the polynomialsf
(
x
)
,
g
(
x
)
∈
Z
[
x
] to be primitive. Since c
o
n
t
f
(
x
) and c
o
n
t
g
(
x
) are defined up to the sign ±
1, we can without loss of generality admit the leading coefficients of f
(
x
)
,
g
(
x
) to be positive.Below, in Problem 4, we will see that for somep the polynomial e
p
(
x
), computed by the Euclidean algorithm in Z
p
[
x
], may not be the image of d
(
x
) and, moreover, its degree may be different from that of d
(
x
). This means that by applying Algorithm 1 to e
p
(
x
) we may not obtain d
(
x
). Assume, however, we have p, which meets the condition p
>
2
·
N
f
,
g and for which(22)
deg
⁡
d
x
=
deg
⁡
e
p
x
.By Corollary 3, a common divisor of f
(
x
)
,
g
(
x
) is d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
) if and only if it is primitive and if its degree is the maximum of degrees of all common divisors. Since φ
p does not change the degree of d
(
x
), we get by Lemma 4 (applied for the field K
=
Z
p) that d
p
(
x
) is g
c
d of f
p
(
x
)
,
g
p
(
x
) in Z
p
[
x
]. This correspondence surely is not one-to-one, because in Z
[
x
]
g
c
d is calculated up to the unit element of Z
[
x
], which is ±
1, whereas in Z
p
[
x
]
g
c
d is calculated up to the unit element of Z
p
[
x
], which can be any nonzero number t
∈
Z
p
∗
=
{
1
,
…
,
p
-
1
}. So the polynomial e
p
(
x
) calculated by the Euclidean algorithm may not be the image d
p
(
x
) of d
(
x
).Example 11.
Forf
(
x
)
=
x
2
+
4
x
+
3 and g
(
x
)
=
x
2
+
2
x
+
1, whichever prime p
>
4 we take, we will get by the Euclidean algorithm (23)
e
p
x
=
g
c
d
f
p
x
,
g
p
x
=
2
x
+
2
∈
Z
p
x
.But in Z
[
x
] we have d
(
x
)
=
x
+
1. So regardless how large p we choose, we will never get φ
p
(
x
+
1
)
=
2
x
+
2.In other words, we are aware that the imaged
p
(
x
) is one of the folds t
·
e
p
(
x
) of e
p
(
x
) for some t
∈
{
1
,
…
,
p
-
1
}, but we are not aware which t is that.The leading coefficientc
0
=
l
c
d
(
x
) of d
(
x
) can also be assumed to be positive. Denote by w the positive g
c
d
(
a
0
,
b
0
). Since both c
0 and w are not altered by φ
p, their fraction w
/
c
0 also is not altered. Take such t that(24)
l
c
t
·
e
p
x
=
w
.Even if t
·
e
p
(
x
) is not the image d
p
(
x
), it is the image of l
·
d
(
x
), where l divides w
/
c
0. If we calculate the preimage k
(
x
)
∈
Z
[
x
] of t
·
e
p
(
x
) by Algorithm 1, we will get a polynomial, which is either d
(
x
) or some fold of d
(
x
). Since f
(
x
)
,
g
(
x
) are primitive, it remains to go to the primitive part d
(
x
)
=
p
p
k
(
x
).The general case, whenf
(
x
)
,
g
(
x
) may not be primitive, can easily be reduced to the following: for arbitrary f
(
x
)
,
g
(
x
), take their decompositions by formula (5) and set(25)
r
=
g
c
d
c
o
n
t
f
x
,
c
o
n
t
g
x
∈
Z
.Then assign f
(
x
)
=
p
p
f
(
x
), g
(
x
)
=
p
p
g
(
x
) and do the steps above for these new polynomials. After d
(
x
)
=
p
p
k
(
x
) is computed, we get the final answer as r
·
d
(
x
)
=
r
·
p
p
k
(
x
).Notice that for Algorithm1 we need p to be greater than any coefficient |
c
i
| of the polynomial we reconstruct. The bound p
>
2
·
N
f
,
g assures that p meets this condition for d
(
x
). We, however, reconstruct not d
(
x
) but l
·
d
(
x
), which may have larger coefficients. One could overcome this point by taking p
>
w
·
2
·
N
f
,
g, but this is not necessary because as we see later, while the Big prime modular g
c
d algorithm works, the value of p will grow and this issue will be covered.


## 4.4. Problem 4: Finding the Right Degree for the Modularg
c
d

As we saw, one can reconstructd
(
x
) if we find p
>
2
·
N
f
,
g such that condition (22) holds. Consider an example to see that (22) may actually not hold for some p even if φ
p is not altering the coefficients of f
(
x
) and g
(
x
)!Example 12.
Forf
(
x
)
=
x
2
+
1 and g
(
x
)
=
x
+
1, we have d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
1. Taking p
=
2 we get f
2
(
x
)
=
x
2
+
1 and g
2
(
x
)
=
x
+
1. In Z
2
[
x
] we have f
2
(
x
)
=
x
2
+
1
=
x
2
+
1
2
=
(
x
+
1
)
(
x
+
1
); thus, e
2
(
x
)
=
g
c
d
(
f
2
(
x
)
,
g
2
(
x
)
)
=
x
+
1. We get that 1
=
deg
⁡
(
x
+
1
)
>
deg
⁡
x
=
0. In particular, whatever t we take, t
·
(
x
+
1
) is not the image of d
(
x
)
=
1 under φ
2.The idea to overcome this problem is to show that the number of primesp, for which (22) falsifies, is “small.” So if the selected p is not suitable, we take another p and do the calculation again by the new prime. And we will not have to repeat these steps for many times (we will turn to this point in Section 6).The proof of the following theorem and the definition of the resultantr
e
s
(
f
(
x
)
,
g
(
x
)
) (i.e., of the determinant of the Sylvester matrix S
f
,
g of polynomials f
(
x
)
,
g
(
x
)) can be found, for example, in [1, 4, 7, 10]. The resultant is a comfortable tool to detect if the given polynomials are coprime.Theorem 13.
LetR be an integrity domain. The polynomials f
(
x
)
,
g
(
x
)
∈
R
[
x
] are coprime if and only if r
e
s
(
f
(
x
)
,
g
(
x
)
)
≠
0.The following fact in a little different shape can be found in [4] or [5].Corollary 14.
If the primep does not divide at least one of the leading coefficients a
0, b
0 of polynomials, respectively, f
(
x
)
,
g
(
x
)
∈
Z
[
x
], then deg
⁡
d
(
x
)
≤
deg
⁡
e
p
(
x
). If p also does not divide R
=
r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
), where d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
), then(26)
deg
⁡
d
x
=
deg
⁡
d
p
x
=
deg
⁡
g
c
d
f
p
x
,
g
p
x
=
deg
⁡
e
p
x
.Proof.
Sincec
0
=
l
c
d
(
x
) divides w
=
g
c
d
(
a
0
,
b
0
), then φ
p
(
c
0
)
≠
0 by the choice of p. Thus, deg
⁡
d
(
x
)
=
deg
⁡
d
p
(
x
)
≤
deg
⁡
g
c
d
f
p
x
,
g
p
x.
Sinced
p
(
x
)
≠
0, we can consider the fractions f
p
(
x
)
/
d
p
(
x
) and g
p
(
x
)
/
d
p
(
x
) in Z
p
[
x
]. From unique factorizations of f
p
(
x
) and g
p
(
x
) in UFD Z
p
[
x
], it is very easy to deduce that (27)
e
p
x
≈
g
c
d
f
p
x
,
g
p
x
≈
d
p
x
·
g
c
d
f
p
x
d
p
x
,
g
p
x
d
p
x
.In particular, deg
⁡
d
(
x
)
=
deg
⁡
d
p
(
x
)
≤
deg
⁡
e
p
(
x
). And the inequality deg
⁡
d
p
(
x
)
≠
deg
⁡
e
p
(
x
) may occur only if (28)
deg
⁡
g
c
d
f
p
x
d
p
x
,
g
p
x
d
p
x
>
0
,that is, when f
p
(
x
)
/
d
p
(
x
) and g
p
(
x
)
/
d
p
(
x
) are not coprime in Z
p
[
x
] or, by Theorem 13, when r
e
s
(
f
p
(
x
)
/
d
p
(
x
)
,
g
p
(
x
)
/
d
p
(
x
)
)
=
0. The latter is the determinant of Sylvester matrix S
f
p
/
d
p
,
g
p
/
d
p. Consider the matrix rings homomorphism (matrix modular reduction) (29)
φ
p
:
M
m
+
n
Z
⟶
M
m
+
n
Z
p
,where n
=
deg
⁡
f
(
x
); m
=
deg
⁡
g
(
x
) (as mentioned earlier we use the same symbol φ
p for numeric, polynomial, and matrix reductions). Since, φ
p
(
S
f
/
d
,
g
/
d
)
=
S
f
p
/
d
p
,
g
p
/
d
p and since the determinant of a matrix is a sum of products of its elements, we get (30)
R
p
=
φ
p
R
=
φ
p
r
e
s
f
x
d
x
,
g
x
d
x
=
r
e
s
f
p
x
d
p
x
,
g
p
x
d
p
x
.So R
p can be zero if and only if R is divisible by p. The polynomials f
(
x
)
/
d
(
x
) and g
(
x
)
/
d
(
x
) are coprime in Z
[
x
] and their resultant is not zero by Theorem 13. And R cannot be a positive integer divisible by p since that contradicts the condition of this corollary.Corollary14 shows that if for some p equality (22) does not hold for polynomials f
(
x
)
,
g
(
x
)
∈
Z
[
x
], then p either divides a
0 and b
0 or divides the resultant R. We do not know R, since we do not yet know d
(
x
) to calculate the resultant R
=
r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
). But since the number of such primes p is just finite, we can arrive to the right p after trying the process for a few primes. We will turn to this again in Section 6.


## 5. The Big Prime Modularg
c
d Algorithm

Four steps of the previous section provide us with the following procedure. We keep all the notations from Section4. Take the primitive polynomials f
(
x
)
,
g
(
x
)
∈
Z
[
x
]. Without loss of generality, we may assume a
0
,
b
0
>
0. Take any p
>
2
·
N
f
,
g. Then p
∤
w
=
g
c
d
(
a
0
,
b
0
), since a
0
,
b
0
≤
N
f
,
g. Calculate e
p
(
x
)
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) in Z
p
[
x
] by Euclidean algorithm. Then choose t so that (24) holds. Construct k
(
x
) applying Algorithm 1 to t
·
e
p
(
x
). If the primitive part d
(
x
)
=
p
p
k
(
x
) divides both f
(
x
) and g
(
x
), then g
c
d for these primitive polynomials is found: d
(
x
)
=
g
c
d
(
f
(
x
)
,
g
(
x
)
). That follows from consideration about divisor degrees above: if f
(
x
)
,
g
(
x
) had a common divisor h
(
x
) of degree greater than deg
⁡
d
(
x
), then, since the degree of h
(
x
) is not altered by φ
p, we would get deg
⁡
h
p
(
x
)
>
deg
⁡
d
p
(
x
)
=
deg
⁡
d
(
x
)
=
deg
⁡
e
p
(
x
), which contradicts the maximality of deg
⁡
d
p
(
x
) by Lemma 4.This means that if forp
>
2
·
N
f
,
g we get d
(
x
)
∤
f
(
x
) or d
(
x
)
∤
g
(
x
), we have the case when p divides the resultant R. Then we just ignore the calculated polynomial, choose another p
>
2
·
N
f
,
g, and redo the steps for it. Repeating these steps for finitely many times, we will eventually arrive to the correct d
(
x
) for the primitive polynomials f
(
x
)
,
g
(
x
).The case of arbitrary nonzero polynomials can easily be reduced to this. By arguments mentioned earlier, we should calculated
(
x
) for primitive polynomials p
p
f
(
x
) and p
p
g
(
x
) and then output the final answer as r
·
d
(
x
), where r is defined by (25). The process we described is the traditional form of the Big prime modular g
c
d algorithm.Remark 15.
Since our approach in Section4 evolved the maximality of degrees of the common divisors, we can shorten some of the steps of our algorithm. Let us store in a variable, say D, the minimal value for which we already know it is not deg
⁡
g
c
d
(
f
(
x
)
,
g
(
x
)
). As an initial D, we may take, for example, D
=
m
i
n
{
deg
⁡
f
x
,
deg
⁡
g
(
x
)
}
+
1. Each time we calculate e
p
(
x
)
=
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
), check if deg
⁡
e
p
(
x
) is equal to or larger than the current D. If yes, we already know that we have an “inappropriate” p. Then we no longer need to use Algorithm 1 to reconstruct k
(
x
) and to get d
(
x
)
=
p
p
k
(
x
). We just skip these steps and proceed to the next p. Reconstruct d
(
x
) and check if d
(
x
)
∣
f
(
x
) and d
(
x
)
∣
g
(
x
)
only when deg
⁡
e
p
(
x
)
<
D. Then, if d
(
x
) does not divide f
(
x
) or g
(
x
), we have discovered a new bound D for deg
⁡
(
g
c
d
(
f
x
,
g
x
)
). So set D
=
deg
⁡
e
p
(
x
) and proceed to the next p. If in next step we get deg
⁡
e
p
(
x
)
≥
D, we will again be aware that the steps of reconstruction of d
(
x
) need be skipped.We constructed Algorithm2.Turning back to Remark15, notice that for some prime numbers p we skip steps (
14
)
–
(
18
) of Algorithm 2 and directly jump to step (
08
). In fact, Remark 15 has mainly theoretical purpose to display how usage of UFD properties and comparison of divisor degrees may reduce some of the steps of the Big prime modular g
c
d algorithm. In practical examples, the set of primes we use contains few primes dividing R
=
r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
), so we may not frequently get examples where steps (
14
)
–
(
18
) are skipped.Example 16.
Let us apply Algorithm2 to polynomials (1) mentioned in Knuth’s example above. Since f
(
x
)
=
113 and g
(
x
)
=
570, (31)
N
f
,
g
=
2
m
i
n
8,6
·
g
c
d
1,3
·
min
⁡
113
1
,
570
3
<
512
.And we can take the prime p
=
1031
>
2
·
N
f
,
g. It is not hard to compute that g
c
d
(
f
1031
(
x
)
,
g
1031
(
x
)
)
≈
1. So f
(
x
) and g
(
x
) are coprime. It is worth to compare p
=
1031 with much smaller values p
=
67 and p
=
37 obtained below for the same polynomials in (1) in Example 27 using modified Algorithm 4.In [1] we also apply Algorithm 2 to other polynomials with cases when the polynomials are not coprime.


## 6. Estimating the Prime Divisors of the Resultant

Although at the start of the Big prime modularg
c
d algorithm we cannot compute the resultant R
=
r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
) for the given f
(
x
)
,
g
(
x
)
∈
Z
[
x
] (we do not know d
(
x
)), we can nevertheless estimate the value of R and the number of its prime divisors. Denote(32)
A
f
,
g
=
n
+
1
m
m
+
1
n
·
N
f
m
N
g
n
=
2
2
n
m
-
n
-
m
n
+
1
m
m
+
1
n
·
f
x
m
g
x
n
.Lemma 17.
For any polynomialsf
(
x
)
,
g
(
x
)
∈
Z
[
x
] and for any of their common divisors d
(
x
), the following holds: (33)
r
e
s
f
x
d
x
,
g
x
d
x
=
S
f
/
d
,
g
/
d
≤
A
f
,
g
.Proof.
By Corollary7, the coefficients of fractions f
(
x
)
/
d
(
x
) and g
(
x
)
/
d
(
x
) are bounded, respectively, by N
f
=
2
n
-
1
f
(
x
) and N
g
=
2
m
-
1
g
(
x
), where n
=
deg
⁡
f
(
x
); m
=
deg
⁡
g
(
x
). Since the numbers of summands in these fractions are at most n
+
1 and m
+
1, respectively, we get (34)
f
x
d
x
≤
n
+
1
N
f
2
,
g
x
d
x
≤
m
+
1
N
g
2
.Applying Hadamard’s maximal determinant bound [4] to the Sylvester matrix S
f
/
d
,
g
/
d, we get that (35)
R
=
S
f
/
d
,
g
/
d
≤
n
+
1
N
f
m
·
m
+
1
N
g
n
.The bound of (32) is very rough. To see this, apply it to polynomials (1) of Knuth’s example.Example 18.
For polynomials (1), we have f
(
x
)
=
113 and g
(
x
)
=
570. So we can estimate N
f
<
1408, N
g
<
768, and N
f
,
g
<
512. Thus (36)
R
≤
8
+
1
6
6
+
1
8
·
140
8
6
·
57
0
8
=
ω
=
1.6505374299582118582810249858265
e
+
48
,which is a too large number to comfortably operate with.Remark 19.
If in Algorithm2 we use a prime(37)
p
>
2
·
A
f
,
g
,then we will get that p
∤
R
=
r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
) whatever the greatest common divisor d
(
x
) is. And, clearly, p
∤
w holds for w
=
g
c
d
(
a
0
,
b
0
). So, in this case, Algorithm 2 will output the correct p
p
k
(
x
) using just one p, and we will not have to take another p
∤
w after step (
18
). However, Example 18 shows why it isnot reasonable to choose p by rule (37) to have in Algorithm 2 one cycle only: it is easier to go via a few cycles for smaller p rather than to operate with a huge p, which is two times larger than the bound ω obtained in Example 18.Nevertheless, the boundA
f
,
g may be useful if we remember that the process in Algorithm 2 concerned not the value of r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
) but thenumber of its distinct prime divisors. Let us denote by p
k
# the product of the first k primes: p
k
#
=
p
1
·
p
2
⋯
p
k (where p
1
=
2, p
2
=
3, etc.). They sometimes call p
k
# the“
k
th primorial.” The following is essential.Lemma 20.
The number of pairwise distinct prime divisors of a positive integern is less than or equal to m
a
x
k
∣
p
k
#
≤
n.From Lemmas17 and 20, we easily get the following.Corollary 21.
For any polynomialsf
(
x
)
,
g
(
x
)
∈
Z
[
x
] and for any of their common divisors d
(
x
), the number of pairwise distinct prime divisors of r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
) is at most k, where k is the largest number for which p
k
#
≤
A
f
,
g.Primorial (as a function onk) grows very rapidly. Say, for k
=
10, it is more than six billions: p
10
#
=
6,469,693,230. This observation allows using the bound A
f
,
g in the following way: although the value of A
f
,
g as a function on n
=
deg
⁡
f
(
x
) and m
=
deg
⁡
g
(
x
) and on the coefficients of f
(
x
) and g
(
x
) grows rapidly, the number of its distinct prime divisors may not be “very large” thanks to the fact that p
k
# also grows rapidly. Consider this on polynomials and values from Example 18.Example 22.
It is easy to compute that(38)
p
30
#
=
3.1610054640417607788145206291544
e
+
46
<
ω
,
p
31
#
=
4.014476939333036189094441199026
e
+
48
>
ω
,where ω is the large number from Example 18. This means that the number of prime divisors of R
=
r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
), whatever the divisor d
(
x
) is, is not greater than 30. And, whichever 30
+
1
=
31 distinct primes we take, at least one of them willnot be a divisor of R. That is, Algorithm 2 for the polynomials of Knuth’s example will output the correct answer in not more than 31 cycles. Wecannot find 31 primes p
∤
w so that Algorithm 2 arrives to a wrong d
(
x
)
=
p
p
k
(
x
) on step (
18
) for all of them.Remark 23.
Let us stress that estimates on the number of prime divisors of the resultant and the analog of Algorithm3 can be found elsewhere, for example, in [4]. So the only news we have is that here we use a slightly better value for N
f and N
g to get 2
n
+
m times smaller bound for A
f
,
g. Namely, in Corollary 7 we estimate c
i not by 2
n
f
(
x
) but by 2
n
-
1
f
(
x
) (see (19) and Remark 8). This makes the bound A
f
,
g in formula (32) 2
n
+
m times lower, since N
f and N
g appear m and n times, respectively.


## 7. An Algorithm to Check Coprime Polynomials

The first application of the bounds found in previous section is an algorithm checking if the given polynomialsf
(
x
)
,
g
(
x
)
∈
Z
[
x
] are coprime. Present the polynomials as f
(
x
)
=
c
o
n
t
f
(
x
)
·
p
p
f
(
x
) and g
(
x
)
=
c
o
n
t
g
(
x
)
·
p
p
g
(
x
). If r
=
g
c
d
(
c
o
n
t
f
(
x
)
,
c
o
n
t
g
(
x
)
)
≉
1, then f
(
x
)
,
g
(
x
) are not coprime, and we do not have to check the primitive parts, at all.Ifr
≈
1, then switch to the polynomials f
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
). By Corollary 21, the number of distinct prime divisors of r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
) is less than or equal to k, where k is the largest number for which p
k
#
≤
A
f
,
g.Consider anyk
+
1 primes p
1
,
…
,
p
k
+
1, each not dividing w
=
g
c
d
(
a
0
,
b
0
), where a
0
=
l
c
f
(
x
) and b
0
=
l
c
g
(
x
). If g
c
d
(
f
p
i
(
x
)
,
g
p
i
(
x
)
)
=
1 for at least one p
i, then f
(
x
) and g
(
x
) are coprime because 0
=
deg
⁡
g
c
d
(
f
p
i
(
x
)
,
g
p
i
(
x
)
)
≥
deg
⁡
g
c
d
(
f
(
x
)
,
g
(
x
)
) and r
≈
1.And ifg
c
d
(
f
p
i
(
x
)
,
g
p
i
(
x
)
)
≠
1 for all i
=
1
,
…
,
k
+
1, then f
p
i
(
x
) and g
p
i
(
x
) are not coprime for at least one p
i, which is not dividing r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
). This means that f
(
x
) and g
(
x
) are not coprime. We got  Algorithm 3.Two important advantages of this algorithm are that here we use much smaller primesp (we just require p
∤
w, not p
>
2
·
N
f
,
g), and in Algorithm 3, unlike in Algorithm 2, we never need to find t, to compute the preimage k
(
x
) of t
·
g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
) and the primitive part p
p
k
(
x
).Remark 24.
As is mentioned by Knuth in [2], in a probabilistic sense, the polynomials are much more likely to be coprime than the integer numbers. So it is reasonable to first test by Algorithm 3 if the given polynomials f
(
x
)
,
g
(
x
) are coprime, and only after that apply Algorithm 2 to find their g
c
d in case if they are not coprime. See also Algorithm 5, where we combine both of these approaches with a better bound for prime p.Example 25.
Apply Algorithm3 to polynomials (1) from Knuth’s example. As we saw in Example 22, k
=
30. For p
=
2, we get f
2
(
x
)
=
x
8
+
x
6
+
x
4
+
x
3
+
1,g
2
(
x
)
=
x
6
+
x
4
+
x
+
1, which are not coprime, since g
c
d
(
f
2
(
x
)
,
g
2
(
x
)
)
=
x
2
+
x
+
1
≠
1. And for p
=
3 we get f
3
(
x
)
=
x
8
+
x
6
+
2
x
2
+
2
x
+
1, g
3
(
x
)
=
2
x
4
+
2
x
2, which are coprime. So g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
1.Example 26.
Iff
(
x
)
=
x
2
+
2
x
+
1 and g
(
x
)
=
x
+
1. Then N
f
=
2
6, N
g
=
2 and A
f
,
g
<
39. Since 2
·
3
·
5
·
7
=
210
>
39, we get that k
=
3, and g
c
d
(
f
(
x
)
,
g
(
x
)
)
≠
1 if g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
)
≠
1 for anyfour primes (not dividing w). It is easy to check that g
c
d
(
f
p
(
x
)
,
g
p
(
x
)
)
≠
1 for p
=
2,3
,
5,7.


## 8. Other Modifications of Algorithms

The bounds mentioned in Section6 can be applied to obtain modifications of Algorithm 2. Let us outline four ideas, of which only the last two will be written down as algorithms.For the nonzero polynomialsf
(
x
)
,
g
(
x
)
∈
Z
[
x
], let us again start by computing r
=
g
c
d
(
c
o
n
t
f
(
x
)
,
c
o
n
t
g
(
x
)
) and switching to the primitive parts f
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
), assuming that their leading coefficients a
0 and b
0 are positive. Calculate N
f, N
g by Corollary 7, N
f
,
g by Corollary 9, and A
f
,
g by (32). Find the maximal k for which p
k
#
≤
A
f
,
g. Then take any k
+
1 primes p
1
,
…
,
p
k
+
1, each greater than 2
·
N
f
,
g. We do not know d
(
x
), but we are aware that the number of prime divisors of R
=
r
e
s
(
f
(
x
)
/
d
(
x
)
,
g
(
x
)
/
d
(
x
)
) is less than or equal to k. So at least one of the primes p
1
,
…
,
p
k
+
1 is not dividing R. To find it, compute the degrees of e
p
i
(
x
) for all i
=
1
,
…
,
k
+
1. Take any p
i, for which deg
⁡
e
p
i
(
x
) is the minimal (in case there is more than one p
i with this property, take one of them, preferably the smallest of all).By our construction,deg
⁡
e
p
i
(
x
)
=
deg
⁡
g
c
d
(
f
(
x
)
,
g
(
x
)
) holds. So we can proceed to the next steps: choose t, such that l
c
t
·
e
p
i
(
x
)
=
w
=
g
c
d
(
a
0
,
b
0
); then find by Algorithm 1 the preimage k
(
x
) of t
·
e
p
i
(
x
); then proceed to its primitive part d
(
x
)
=
p
p
k
(
x
); and then output the final answer as r
·
d
(
x
).The advantage of this approach is that we do not have to go via steps(
14
)
–
(
18
) of Algorithm 2 for more than one prime p. Also, we do not have to take care of the variable D. But the disadvantage is that we have to compute e
p
i
(
x
) for large primes for k
+
1 times (whereas in Algorithm 2 the correct answer could be discovered after consideration of fewer primes). Clearly, the disadvantage is a serious obstacle, since repetitions for k
+
1 large primes consume more labour than steps (
14
)
–
(
18
) of Algorithm 2. So this is just a theoretical idea, not an approach for an effective algorithm.The disadvantage can be reduced in the following way: in previous arguments, after we findp
k
# and k, select the prime numbers p
1
,
…
,
p
k
+
1 each satisfying the condition p
i
∤
w. This is a much weaker condition than the condition p
i
>
2
·
N
f
,
g used above, so we will surely get smaller primes. Take M to be the minimum of all degrees deg
⁡
e
p
i
(
x
) for all i
=
1
,
…
,
k
+
1. Since none of the primes p
1
,
…
,
p
k
+
1 divides w, for any i
=
1
,
…
,
k
+
1, we have deg
⁡
e
p
i
(
x
)
≥
deg
⁡
g
c
d
(
f
(
x
)
,
g
(
x
)
). On the other hand, since at least one of the primes p
1
,
…
,
p
k
+
1 does not divide R, we know that, for that p
i, the degree of e
p
i
(
x
) is equal to deg
⁡
g
c
d
(
f
(
x
)
,
g
(
x
)
). Combining these, we get that deg
⁡
g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
M. Since we know M, we can take a prime p
>
2
·
N
f
,
g and compute e
p
(
x
) and check its degree: if deg
⁡
e
p
(
x
)
≠
M, then we have a wrong p (we no longer need go to steps (
14
)
–
(
18
) of Algorithm 2 to discover that). Then choose a new value for p and repeat the step. And if deg
⁡
e
p
(
x
)
=
M, then we have the right p. We calculate t, the preimage k
(
x
) of t
·
e
p
i
(
x
), and then d
(
x
)
=
p
p
k
(
x
), and output the answer r
·
d
(
x
) (see Algorithm 5 for a better version of this idea).The third modification, not depending onA
f
,
g, can be constructed by estimating deg
⁡
g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
deg
⁡
d
(
x
) by means of an auxiliary prime number q. By Landau-Mignotte Theorem 6, if h
(
x
)
=
c
0
x
k
+
⋯
+
c
k is any divisor of the polynomials f
(
x
)
=
a
0
x
n
+
⋯
+
a
n and g
(
x
)
=
b
0
x
m
+
⋯
+
b
m, then |
c
i
|
≤
2
k
|
c
0
/
a
0
|
f
(
x
) and |
c
i
|
≤
2
k
|
c
0
/
b
0
|
g
(
x
). Since |
c
0
/
a
0
| is bounded by |
g
c
d
(
a
0
,
b
0
)
/
a
0
| and |
c
0
/
b
0
| is bounded by |
g
c
d
(
a
0
,
b
0
)
/
b
0
|, we get the following analog of (20):(39)
c
i
≤
2
k
·
g
c
d
a
0
,
b
0
·
min
⁡
f
x
a
0
,
g
x
b
0
.Now assumeq is a prime not dividing w, and denote s
(
q
,
f
,
g
)
=
deg
⁡
g
c
d
(
f
q
(
x
)
,
g
q
(
x
)
). By Corollary 14, deg
⁡
d
(
x
)
≤
s
(
q
,
f
,
g
). We get for the coefficients of d
(
x
) the following bound: |
c
i
|
≤
M
q
,
f
,
g, where(40)
M
q
,
f
,
g
=
2
s
q
,
f
,
g
·
g
c
d
a
0
,
b
0
·
min
⁡
f
x
a
0
,
g
x
b
0
.
M
q
,
f
,
g is a better bound for the coefficients of d
(
x
) because 2
s
(
q
,
f
,
g
) may be considerably less than 2
m
i
n
{
n
,
m
}.We can improve Algorithm2, if we preliminarily find s
(
q
,
f
,
g
) by calculating g
c
d
(
f
q
(
x
)
,
g
q
(
x
)
) for an “auxiliary” prime q
∤
w and then choose the “main” prime p by the rule p
>
2
·
M
q
,
f
,
g (instead of p
>
2
·
N
f
,
g). Observe that if p
>
2
·
M
q
,
f
,
g then also q
∤
w
=
g
c
d
(
a
0
,
b
0
) because m
i
n
f
(
x
)
/
|
a
0
|
,
g
(
x
)
/
|
b
0
|
≥
1. Additionally, we can introduce the variable D to store the values deg
⁡
g
c
d
f
p
x
,
g
p
x that we know are greater than deg
⁡
d
(
x
). We get  Algorithm 4.Example 27.
Let us apply Algorithm4 to polynomials (1) from Knuth’s example. Since w
=
1, take q
=
2. We have already computed in Example 25 that e
2
(
x
)
=
g
c
d
(
f
2
(
x
)
,
g
2
(
x
)
)
=
x
2
+
x
+
1. Then s
(
2
,
f
,
g
)
=
deg
⁡
e
2
(
x
)
=
2 and (41)
M
2
,
f
,
g
=
2
2
·
1
·
min
⁡
113
1
,
570
3
<
31.84
.Take p
=
67
>
2
·
M
2
,
f
,
g. It is easy to calculate that g
c
d
(
f
67
(
x
)
,
g
67
(
x
)
)
≈
1. Compare this with Example 16, where we had to use much larger prime p
=
1031. Moreover, if we take as an auxiliary q, say q
=
3, then s
(
3
,
f
,
g
)
=
deg
⁡
e
3
(
x
)
=
0 and M
3
,
f
,
g
≤
15.92
. So we can take an even smaller prime p
=
37
>
2
·
M
3
,
f
,
g.The ideas of Algorithms3 and 4 can be combined to work with more than one auxiliary prime q. Like we mentioned in Remark 24, Knuth in [2] recommends checking first if the polynomials f
(
x
)
,
g
(
x
)
∈
Z
[
x
] are coprime and proceeding to their g
c
d calculation only after we get that they are not coprime (this is motivated by probabilistic arguments). Compute A
f
,
g by formula (32) and find k like we did in step (
09
) of Algorithm 3: k is the maximal number for which p
k
#
≤
A
f
,
g. Then choose any k
+
1 primes q
1
,
…
,
q
k
+
1 not dividing w, and start computing the modular g
c
d’s e
q
1
(
x
)
,
e
q
2
(
x
)
,
… (k
+
1 times). If at some step we find deg
⁡
e
q
i
(
x
)
=
0, then we are done: the polynomials f
(
x
)
,
g
(
x
) are coprime if r
≈
1, or their g
c
d is the nontrivial scalar r
≉
1. And if deg
⁡
e
q
i
(
x
)
>
0 for all q
i, then we know that(1)
these polynomials are not coprime,
(2)
the positive degree ofg
c
d
(
f
(
x
)
,
g
(
x
)
) is the minimum(42)
s
f
,
g
=
min
⁡
deg
⁡
e
q
1
x
,
…
,
deg
⁡
e
q
k
+
1
x
>
0
.This exact value of s
(
f
,
g
)
=
deg
⁡
g
c
d
(
f
(
x
)
,
g
(
x
)
) is a better result than the estimate s
(
q
,
f
,
g
) obtained earlier by just one q.Like above, we can assumef
(
x
)
,
g
(
x
) to be primitive (if not, we can again denote r
=
g
c
d
(
c
o
n
t
f
(
x
)
,
c
o
n
t
g
(
x
)
) and switch to the primitive parts f
(
x
)
=
p
p
f
(
x
) and g
(
x
)
=
p
p
g
(
x
)). Applying the Landau-Mignotte Theorem 6 for the coefficients c
i of g
c
d
(
f
(
x
)
,
g
(
x
)
), we get that |
c
i
|
≤
M
f
,
g, where(43)
M
f
,
g
=
2
s
f
,
g
·
g
c
d
a
0
,
b
0
·
min
⁡
f
x
a
0
,
g
x
b
0
.Now we can takep
>
2
·
M
f
,
g and by the Euclidean algorithm calculate e
p
(
x
) in Z
p
[
x
]. If deg
⁡
e
p
(
x
)
>
s
(
f
,
g
), we drop this p and choose another prime p
>
2
·
M
f
,
g. And if deg
⁡
e
p
(
x
)
=
s
(
f
,
g
), then we proceed to the final steps: we choose t, then get the preimage k
(
x
) of t
·
e
p
(
x
), then go to the primitive part d
(
x
)
=
p
p
k
(
x
), and output the final answer as g
c
d
(
f
(
x
)
,
g
(
x
)
)
=
r
·
p
p
k
(
x
).Remark 28.
This approach has the following advantages: Firstly, the bound on primesp is better than formula (40) since here we have not 2
s
(
q
,
f
,
g
) but 2
s
(
f
,
g
). Secondly, we no longer need to calculate the number t, the preimage k
(
x
), and the primitive part d
(
x
) formore than one prime p. This is because, if the selected p
>
2
·
M
f
,
g is not appropriate, we already have an indicator of that: deg
⁡
e
p
(
x
)
>
s
(
f
,
g
).We built Algorithm5.Example 29.
Let us apply Algorithm5 again on polynomials of Knuth’s example (1). As we saw in Example 22, k
=
30. So we may have to consider at most 31 auxiliary primes q
i. But we in fact need just two of them, because deg
⁡
g
c
d
(
f
2
(
x
)
,
g
2
(
x
)
)
=
deg
⁡
(
x
2
+
x
+
1
)
=
2 and deg
⁡
g
c
d
(
f
3
(
x
)
,
g
3
(
x
)
)
=
deg
⁡
(
1
)
=
0 (see Example 25). So in Algorithm 5 we jump from step (
16
) to step (
32
) directly.



---

*Source: 3262450-2016-10-05.xml*