§1. Chinese Remainder Theorem  Lecture IV  Page 1

Lecture IV Modular Techniques: Chinese Remainder

We introduce modular techniques based on the Chinese Remainder Theorem. This leads to a more efficient GCD algorithm in [X].

Unlike the previous lecture, the rings in here need not be domains.

§1. Chinese Remainder Theorem

The Chinese Remainder Theorem stems from observations about integers such as these: assume we are interested in computing with non-negative integers that are no larger than 3 · 4 · 5 = 60. Then any integer of interest, say 18, can be represented by its vector of residues modulo 3, 4, 5 (respectively),

(18 mod 3, 18 mod 4, 18 mod 5) = (0, 2, 3).

Two numbers in this representation can be added and multiplied, in the obvious componentwise manner. It turns out this sum or product can be faithfully recovered provided it does not exceed 60. For instance 36 = 18 × 2 is represented by (0, 2, 3) × (2, 2, 2) = (0, 0, 1), which represents 36. A limited form of the theorem was stated by Sun Tsu (between 280 and 473 A.D.); the general statement and proof came much later (from Shu Shu Chiu Chang, in 1247).

We proceed to put these ideas its proper algebraic setting (following Lauer [2]). The above illustration uses an implicit ring, _{3} ⊗ _{4} ⊗ _{5}. In general, if R_{1},…, R_{n} are rings, we write

R_{1} ⊗ R_{2} ⊗ ⋯ ⊗ R_{n} or ⨂_{i=1}^{n} R_{i}

for the Cartesian product of R_{1},…, R_{n}, endowed with a ring structure by componentwise extension of the individual ring operations. The zero and unity elements of this Cartesian product are (0, 0,…, 0) and (1, 1,…, 1), respectively. For instance, (u_{1},…, u_{n})+(v_{1},…, v_{n}) = (u_{1} + v_{1},…, u_{n} + v_{n}) where the ith component arithmetic is done in R_{i}. The reader should always keep in sight where the ring operations are taking place because our notations (to avoid clutter) will not show this explicitly.

Let R be a ring. Two ideals I, J ⊆ R are relatively prime if I + J = R. This is equivalent to the existence of a ∈ I, b ∈ J such that a + b = 1. For an ideal I, let R/I denote quotient ring whose elements are denote u + I (u ∈ R) under the canonical map. For example, if R = and I = (n) then R/I is isomorphic to _{n}. Two ideals (n) and (m) are relatively prime iff n, m are relatively prime integers. So the ideals (3), (4), (5) implicit in our introductory example are relatively prime. We now present the ideal-theoretic version of the Chinese Remainder Theorem.

Theorem 1 (Chinese Remainder Theorem) Let (I_{1},…, I_{n}) be a sequence of pairwise relatively prime ideals of R. Then the map

Φ : u ∈ R ⟼ (u + I_{1},…, u + I_{n}) ∈ ⨂_{i=1}^{n}(R/I_{i})

is an onto homomorphism with kernel

ker Φ = ⋂_{i=1}^{n} I_{i}.

In short, this is the content of the Chinese Remainder Theorem:

R/(ker Φ) ≅ (R/I_{1}) ⊗ ⋯ ⊗ (R/I_{n}).

Proof. It is easy to see that Φ is a homomorphism with kernel ⋂_{i=1}^{n} I_{i}. The nontrivial part is to

show that Φ is onto. Let

\overline{u} = (u_{1} + I_{1},…, u_{n} + I_{n}) ∈ ⨂_{i=1}^{n}(R/I_{i}).

We must show the existence of u ∈ R such that Φ(u) = \overline{u}, i.e.,

u ≡ u_{i}(mod I_{i}) for all i = 1,…, n.  (1)

Suppose for each i = 1,…, n we can find b_{i} such that for all j = 1,…, n,

b_{i} ≡ δ_{i,j}(mod I_{j})  (2)

where δ_{i,j} is Kronecker’s delta-function. Then the desired u is given by

u:= ∑_{i=1}^{n} u_{i}b_{i}.

To find the b_{i}’s, we use the fact that for all i ≠ j, I_{i} and I_{j} are relatively prime implies there exist elements

a_{i}^{(j)} ∈ I_{i}

such that

a_{i}^{(j)} + a_{j}^{(i)} = 1.

We then let

b_{i} := ∏_{j≠i^{j=1}}^{n} a_{j}^{(i)}.

To see that b_{i} satisfies equation (2), note that if j ≠ i then a_{j}^{(i)} | b_{i} and a_{j}^{(i)} ∈ I_{j} imply b_{i} ≡ 0(mod I_{j}). On the other hand,

b_{i} = ∏_{j≠i^{j=1}}^{n}(1 − a_{i}^{(j)}) ≡ 1(mod I_{i}).

Q.E.D.

§2. Evaluation and Interpolation  Lecture IV  Page 3

In our introductory example we have R = and the ideals are I_{i} = (q_{i}) where q_{1},…, q_{n} are pairwise relatively prime numbers. The numbers a_{i}^{(j)} can be computed via the extended Euclidean algorithm, applied to each pair q_{i}, q_{j}. The kernel of this homomorphism is the ideal (q_{1}q_{2} ⋯ q_{m}).

The use of the map Φ gives the name “homomorphism method” to this approach. The hope offered by this theorem is that computation in the quotient rings R/I_{i} may be easier than in R. It is important to notice the part of theorem stating that the kernel of the homorphism is ∩_{i=1}^{n}I_{n}. Translated, the price we pay is that elements that are equivalent modulo ∩_{i=1}^{n}I_{n} are indistinguishable.

Lagrange and Newton interpolations. The proof of the Chinese Remainder Theorem involves constructing an element u that satisfies the system of modular equivalences (1). This is the modular interpolation problem. Conversely, constructing the u_{i}’s from u is the modular evaluation problem. The procedure used in our proof is called Lagrange interpolation. An alternative to Lagrange interpolation is Newton interpolation. The basic idea is to build up partial solutions. Suppose we want to solve the system of equivalences u ≡ u_{i}(mod I_{i}) for i = 1,…, n. We construct a sequence u^{(1)},…, u^{(n)} where u^{(i)} is a solution to the first i equivalences. We construct u^{(i)} from u^{(i−1)} using

u^{(i)} = u^{(i−1)} + (u_{i} − u^{(i−1)}) ∏_{j=1}^{i−1} a_{j}^{(i)}

where the a_{j}^{(i)} ∈ I_{j} are as in the Lagrange method. Lagrange interpolation is easily parallelizable, while Newton interpolation seems inherently sequential in nature. On the other hand, Newton interpolation allows one to build up partial solutions in an on-line manner.

Exercise 1.1: Carry out the details for Newton interpolation.

Exercise 1.2: Give an efficient parallel implementation of the Lagrange interpolation.

§2. Evaluation and Interpolation

Polynomial evaluation and interpolation. An important special case of solving modular equivalences is when R = F [X] where F is a field. For any set of n distinct elements, a_{1},…, a_{n} ∈ F, the set of ideals Ideal(X − a_{1}),…, Ideal(X − a_{n}) are pairwise relatively prime. It is not hard to verify by induction that

Ideal(X − a_{1}) ∩ Ideal(X − a_{2}) ∩ ⋯ ∩ Ideal(X − a_{n}) = ∏_{i=1}^{n} Ideal(X − a_{i}) = Ideal(∏_{i=1}^{n} X − a_{i}).

It is easy to see that P (X) mod(X − a_{i}) is equal to P (a_{i}) for any P (X) ∈ F [X] (Lecture VI.1). Hence the quotient ring F [X]/(X − a_{i}) is isomorphic to F. Applying the Chinese Remainder Theorem with I_{i}:=(X − a_{i}), we obtain the homomorphism

Φ : P (X) ∈ F [X] ↦ (P (a_{1}),…, P (a_{n})) ∈ F^{n}.

Computing this map Φ is the polynomial evaluation problem; reconstructing a degree n − 1 polynomial P (X) from the pairs (a_{1}, A_{1}),…, (a_{n}, A_{n}) such that P (a_{i}) = A_{i} for all i = 1,…, n is the polynomial interpolation problem. A straight forward implementation of polynomial evaluation has algebraic complexity O(n^{2}). In Lecture I, we saw that evaluation and interpolation at the n roots of unity has complexity O(n log n). We now show the general case can be solved almost as efficiently.

The fundamental observation which is exploited for polynomial evaluation is this: If M(X)|M′(X) then

P (X) mod M′(X) = (P (X) mod M(X)) mod M′(X).  (3)

Theorem 2 The evaluation of degree n − 1 polynomials at n arbitrary points has algebraic complexity O(n log^{2} n).

Proof. We may assume P (X) is monic and the degree of polynomial P (X) is n − 1, where n = 2^{k} is a power of 2. Suppose we want evaluate P (X) at a_{0},…, a_{n−1}. We construct a balanced binary tree T on n leaves. The n leaves are associated with the polynomials X − a_{j} for j = 0,…, n − 1. If an internal node u has children v, w with associated polynomials M_{v}(X), M_{w}(X) then u is associated with the polynomial M_{u}(X) = M_{v}(X)M_{w}(X). There are 2^{i} polynomials at level i, each of degree 2^{k−i} (the root has level 0). Hence, computing all the polynomials associated with level i takes O(2^{i}(k − i)2^{k−i}) = O(n log n) operations. Hence we can proceed in a bottom-up manner to compute all the polynomials associated with the nodes of T, in O(n log^{2} n) operations.

We call T the moduli tree with respect to a_{0},…, a_{n−1}. This terminology is justified by our intended use for T: given the polynomial P (X), we want to compute

P_{u}(X) := P (X) mod M_{u}(X)

at each node u in T. This is easy to do in a top-down manner. If node u is the child of v and P (X) mod M_{v}(X) has been computed, then we can compute P_{u}(X) via

P_{u}(X) ← P_{v}(X) mod M_{u}(X),

by exploiting equation (3). If u is at level i ≥ 1 then this computation takes O((k − i)2^{k−i}) operations since the polynomials involved have degree at most 2^{k−i+1}. Again, the computation at each level takes O(n log n) operations for a total of O(n log^{2} n) operations. Finally, note that if u is a leaf node with M_{u}(X) = X − a_{j}, then P_{u}(X) = P (X) mod M_{u}(X) = P (a_{j}), which is what we wanted. Q.E.D.

To achieve a similar result for interpolation, we use Lagrange interpolation. In the polynomial case, the formula to interpolate (a_{1}, A_{1}),…, (a_{n}, A_{n}) has a simple form:

P (X) := ∑_{k=1}^{n} Δ_{k}(X)A_{k}

where

Δ_{k}(X) := D_{k}(X)/d_{k}:= (∏_{i≠k^{i=1}}^{n}(X − a_{i})) /(∏_{i≠k^{i=1}}^{n}(a_{k} − a_{i})) .

Note that Δ_{k}(X) has degree n − 1 and Δ_{k}(a_{i}) = δ_{k,i} (Kronecka’s delta), so that P (X) is our desired function. Let us first consider the problem of computing the d_{k}’s. Let

M(X) := ∏_{i=1}^{n}(X − a_{i})

M′(X) = \frac{dM(X)}{dX}

= ∑_{k=1}^{n} (∏_{i≠k^{i=1}}^{n}(X − a_{i}))

Then it is easy to see that M′(a_{k}) = d_{k}. It follows that computing d_{1},…, d_{n} is reduced to evaluating M′(X) at the n points X = a_{1},…, X = a_{n}. By the previous theorem, this can be accomplished with O(n log^{2} n) ring operations.

We now seek to split P (X) into two subproblems. First, write M(X) = M_{0}(X)M_{1}(X) where

M_{0}(X) = ∏_{i=1}^{n/2}(X − a_{i}), M_{1}(X) = ∏_{i=1+n/2}^{n}(X − a_{i}).

Note that M_{0}(X), M_{1}(X) are polynomials in the moduli tree T which we may assume has been precomputed as well. Then

P (X) = ∑_{k=1}^{n/2} Q_{k}(X)\frac{A_{k}}{q_{k}} + ∑_{k=1+n/2}^{n} Q_{k}(X)\frac{A_{k}}{q_{k}}

= M_{1}(X) ∑_{k=1}^{n/2} Q_{k}^{∗}(X)\frac{A_{k}}{q_{k}} + M_{0}(X) ∑_{k=1+n/2}^{n} Q_{k}^{∗}(X)\frac{A_{k}}{q_{k}}
= M_{1}(X)P_{0}(X) + M_{0}(X)P_{1}(X),

where Q_{k}^{∗}(X) = Q_{k}(X)/M_{1}(X) for k ≤ n/2 and Q_{k}^{∗}(X) = Q_{k}(X)/M_{0}(X) for k > n/2, and P_{0}(X), P_{1}(X) have the same form as P (X) except they have degree n/2. By recursively solving for P_{0}(X), P_{1}(X), we can reconstruct P (X) in two multiplications and one addition. The multiplications take O(n log n) time, and so we see that the time T (n) to compute P (X) (given the moduli tree and the q_{k}’s) satisfies the recurrence

T (n) = 2T (n/2) + Θ(n log n)

which has solution T (n) = Θ(n log^{2} n). It follows that the overall problem has this same complexity. This proves:

Theorem 3 The interpolation of a degree n − 1 polynomial from its values at n distinct points has algebraic complexity O(n log^{2} n).

Solving integer modular equations. There are similar results for the integer case, which we only sketch since they are similar in outline to the polynomial case.

Lemma 4 Given s + 1 integers u and q_{1},…, q_{s} where u ∏_{i=1}^{s} q_{i} has bit size of d, we can form

u_{1},…, u_{s} where u_{i} = (u mod q_{i}) in O(dL^{2}d) bit operations.

§3. Prime Moduli  Lecture IV  Page 6

Proof. We proceed in two phases:

1. Bottom-up Phase: Construct a balanced binary tree T with s leaves. On each leaf, we associate a q_{i} and at each internal node v, we associate the product m_{v} of the values at its two children. The product of all m_{v} associated to nodes v in any single level has at most d bits. Proceeding in a bottom-up manner, the values at a single level can be computed in time O(dL(d)). Summing over all log s levels, the time is at most O(d log sL(d)).

2. Top-down Phase: Our goal now is to compute at every node v the value u mod m_{v}. Proceeding “top-down”, assuming that u mod m_{v} at a node v has been computed, we then compute the value u mod m_{w} at a child w of v. This takes time O(M_{B}(log m_{v})). This work is charged to the node v. Summing the work at each level, we get O(dLd). Summing over all levels, we get O(d log sLd) = O(dL^{2}d) time. Q.E.D.

Lemma 5 Given non-negative u_{i}, q_{i} (i = 1,…, s) where u_{i} < q_{i}, the q_{i}’s are pairwise relatively

prime, and ∏_{i=1}^{s} q_{i} has bit size ≤ d, we can compute u satisfying u ≡ u_{i}(mod q_{i}) in bit complexity

O(sdL^{2}(d)) = O(d^{2}L^{2}(d)).

Proof. Let d_{i} denote the bit size of q_{i} (so d = ∑_{i=1}^{s} d_{i}). We use the terminology in the proof of the Chinese Remainder Theorem in §1.

1. Each a_{i}^{(j)}, a_{j}^{(i)} is obtained by computing the extended Euclidean algorithm on q_{i}, q_{j}. This takes time O(d_{i} + d_{j})L^{2}(d). Summing over all i ≠ j, we get a bound of O(sdL^{2}(d)).

2. We construct a balanced binary tree T with s leaves, as in the previous lemma. The time is O(d log sL(d)).

3. Using the values in T, we can compute each product b_{i} = ∏_{j=1,j≠i}^{n} a_{j}^{(i)} in time O(d log sL(d)). Summing over all i = 1,…, s, the time becomes O(sd log sL(d)).

4. Finally, we compute u = ∑_{i=1}^{s} u_{i}b_{i}. Each term in this sum can be computed in time O(dL(d)). Thus the sum can be computed in O(sdL(d)) time.

5. Summing over all the above, we get a bound of O(sdL^{2}(d)). Q.E.D.

Exercise 2.1: Solve the following modular interpolation problems:

i) u ≡ 1(mod 2), u ≡ 1(mod 3), u ≡ 1(mod 5). (Of course, we know the answer, but you should go through the general procedure.) ii) u ≡ 1(mod 2), u ≡ 1(mod 3), u ≡ 1(mod 5), u ≡ 3(mod 7). iii) P (0) = 2, P (1) = −1, P (2) = −4, P (3) = −1 where deg P = 3.

Exercise 2.2:

i) Verify the assertions about polynomial evaluation and interpolation.

ii) Let J = Ideal(X − a) ∩ Ideal(X − b) where a, b ∈ F are distinct. Prove that F [X]/J and F [X]/Ideal(X^{2}) are not isomorphic as rings.

§3. Finding Prime Moduli

To apply the Chinese Remainder Theorem in , we need to find a set of relatively prime numbers whose product is sufficiently large. In this section, we show how to find a set of prime numbers whose product is larger than some prescribed bound.

§4. Lucky homomorphisms  Lecture IV  Page 7

The following function is useful: for a positive integer n, θ(n) is defined to be the natural logarithm of the product of all primes ≤ n. The following estimate from Langemyr [7] (see also Rosser-Schoenfeld [8]) is useful.

Proposition 6 For n ≥ 2,

0.31n < θ(n) < 1.02n.

Consider the following problem: given a number N > 0, list all the primes ≤ N. We can do this quite simply by applying the sieve of Eratosthenes (276-194 B.C.): Let L be a Boolean array of length N, initialized to 1. We want L[i] = 1 to indicate the i is a candidate for a prime. We can immediate set L[1] = 0. In the general step, let p be the smallest index such that L[p] = 1, and p is prime. Then we do the following “step” repeatedly, until the entire array is set to 0:

Output p and set L[ip] = 0 for i = 1, 2,…, ⌊\frac{N}{p} ⌋.  (4)

The correctness of this procedure is well-known. Note that (4) costs \frac{N}{p} array accesses. The total number of array accesses over all steps is

∑_{p<N} \frac{N}{p} = N · ∑_{p<N} \frac{1}{p}.

Clearly ∑_{p<N} \frac{1}{p} ≤ ∑_{i=1}^{N} \frac{1}{i} = O(log N). But it is well-known in number theory [3, p.351] that

∑_{p<N} \frac{1}{p} = log log N + O(1).

So the total number of array accesses is O(N log log N). In the RAM complexity model, this procedure has a complexity of O(NL(N)).

Lemma 7 We can find a list of primes whose product is at least n in time O(log nL(log n)) in the RAM model.

Proof. Choose N = ⌈\frac{ln n}{0.31}⌉. Then θ(N) > 0.31N ≥ ln n. So the product of all primes at most N is at least n. The above algorithm of Erathosthenes gives us the desired complexity bound. Q.E.D.

§4. Lucky homomorphisms for GCD

We now apply the modular technique to computing GCD in [X].

Let p be a fixed prime. The key homomorphism we consider is

(·)_{p} : [X] → _{p}[X]

where (A)_{p} denotes the polynomial obtained by the modulo p reduction of each coefficient of A ∈ [X]. Where there is no ambiguity, we write A_{p} for (A)_{p}. If we view A_{p} as an element of [X], we can also write

A ≡ A_{p}(mod p).

Note that GCD is meaningful in _{p}[X] since it is a UFD. Observe that

(AB)_{p} = (A_{p} · B_{p}), A, B ∈ [X]

where the second product occurs in _{p}[X]. It follows that

A|B implies A_{p}|B_{p}.

Similarly, if GCD(A, B) = AA′ + BB′ then GCD(A, B)_{p} = A_{p}A′_{p} + B_{p}B′_{p}, which divides GCD(A_{p}, B_{p}). Hence

GCD(A, B)_{p}|GCD(A_{p}, B_{p}).

It is not true that

GCD(A, B)_{p} = GCD(A_{p}, B_{p}).  (5)

A simple example is

A = X − 1, B = X + 1

and p = 2. Here A_{p} = B_{p} and hence GCD(A_{p}, B_{p}) = A_{p}. But A, B are relatively prime so that GCD(A, B)_{p} = 1.

The conditions under which equation (5) holds is the subject of this section. Roughly speaking, we call such a choice of p “lucky”. The basic strategy for the modular GCD algorithm is this: we pick a set p_{1},…, p_{n} of lucky primes and compute GCD(A_{p_{i}}, B_{p_{i}}) for i = 1,…, n. Since GCD(A_{p_{i}}, B_{p_{i}}) = GCD(A, B)_{p_{i}}, we can reconstruct G = GCD(A, B) by solving the system of modular equivalences

G ≡ GCD(A, B)_{p_{i}} (mod p_{i}).

Definition: A prime p ∈ is lucky for A, B ∈ [X] if p does not divide lead(A) and p does not divide lead(B) and furthermore

deg(GCD(A_{p}, B_{p})) = deg(GCD(A, B)).

To be sure, this definition sounds odd because we are trying to compute GCD(A, B) via mod p computation, but the definition of luckiness assumes we know the degree of GCD(A, B).

Lemma 8 If p does not divide at least one of lead(A) and lead(B) then GCD(A_{p}, B_{p}) has degree at least as large as GCD(A, B).

Proof. Say p does not divide lead(A). Then p does not divide lead(GCD(A, B)). Hence deg GCD(A, B) = deg GCD(A, B)_{p}. But deg GCD(A, B)_{p} ≤ deg GCD(A_{p}, B_{p}). Q.E.D.

We now generalize this lemma: suppose we have a homomorphism between domains,

Φ : D → D′

extended to

Φ : D[X] → D′[X]

in the coefficient-wise fashion (but still denoted by the same symbol Φ). Let

(A_{m}, A_{m−1},…, A_{0})

be a subresultant chain in D[X] and

(\overline{A}_{m}, \overline{A}_{m−1},…, \overline{A}_{0})

be the Φ-image of the chain, \overline{A}_{i} = Φ(A_{i}). The following is immediate.

Lemma 9 If deg(A_{m}) = deg(\overline{A}_{m}) and deg(A_{m−1}) = deg(\overline{A}_{m−1}) then (\overline{A}_{m},…, \overline{A}_{0}) is a subresultant chain in D′[X].

The hypothesis of this lemma is simply that the leading coefficients of A_{m−1} and A_{m} must not be in the kernel of Φ.

Lemma 10 Under the same assumption as the previous lemma, if \overline{A}_{i} (i = 0,…, m) is nonzero then deg(\overline{A}_{i}) also occurs as deg(A_{j}) for some j ≤ i. In particular, GCD(\overline{A}_{m}, \overline{A}_{m−1}) has degree at least as large as that of GCD(A_{m}, A_{m−1}).

Proof. By the fundamental theorem of PRS, if deg(\overline{A}_{i}) = j then \overline{A}_{j} is regular and hence A_{j} is regular. Q.E.D.

We justify our definition of luckiness:

Lemma 11 (Luckiness Lemma) If p is lucky for A and B then GCD(A_{p}, B_{p}) ∼ GCD(A, B)_{p}.

Proof. Let (A_{m},…, A_{0}) be the subresultant chain for A, B and \overline{A}_{i} = (A_{i})_{p} for i = 0,…, m. Since p is lucky, then lemma (9) implies that (\overline{A}_{m},…, \overline{A}_{0}) is a subresultant sequence for A_{p}, B_{p}. By definition, p is lucky means that if GCD(A, B) has degree k then \overline{A}_{k} and A_{k} are the last nonzero polynomials in their respective subresultant sequence. The lemma follows from

GCD(A, B)_{p} ∼ (A_{k})_{p} = \overline{A}_{k} ∼ GCD(A_{p}, B_{p}).

Q.E.D.

Lemma 12 Let A, B ∈ [X] with n = max{deg A, deg B}, and N = max{∥A∥_{2}, ∥B∥_{2}}. If P is the product of all the unlucky primes of A, B, then

P ≤ N^{2n+2}.

Proof. If GCD(A, B) has degree d then the dth principal subresultant coefficient C_{d} is nonzero. All unlucky primes for A, B are among the divisors of a · b · C_{d}, where a = lead(A) and b = lead(B). The product of all prime divisors of a · b · C_{d} is at most |a · b · C_{d}|. Since |a| ≤ N, |b| ≤ N, the lemma follows from

|C_{d}| ≤ N^{2n}.

§5. Coefficient Bounds  Lecture IV  Page 10

To see this, C_{d} is the determinant of a submatrix M of the Sylvester matrix of A, B. Each row r_{i} of M has non-zero entries coming from coefficients of A or of B. Thus ∥r_{i}∥_{2} ≤ N. Since M has at most 2n rows, the bound on |C_{d}| follows immediately from Hadamard’s determinant bound. Q.E.D.

In other words, the following diagram commutes if p is lucky:

[figure: (A, B); (A_{p}, B_{p}); subres(A, B); subres(A, B)_{p}=subres(A_{p}, B_{p}); mod p; mod p; subres; subres]

Here, subres(P, Q) denotes the subresultant chain of P, Q in the [X] or _{p}[X].

§5. Coefficient Bounds for Factors

Given polynomials A(X), B(X) ∈ [X] where B|A, we want to upper bound ∥B∥_{2} in terms of ∥A∥_{2}. Begin with the following equality:

Lemma 13 Let A(X) ∈ [X], c ∈ . Then ∥(X − c) · A(X)∥_{2} = ∥(\overline{c}X − 1) · A(X)∥_{2}, where \overline{c} is the complex conjugate of c.

Proof. If A(X) = ∑_{i=0}^{m} a_{i}X^{i} then

(X − c) · A(X) = ∑_{i=0}^{m+1}(a_{i−1} − ca_{i})X^{i},  (a_{−1} = a_{m+1} = 0),

∥(X − c) · A(X)∥_{2} = ∑_{i=0}^{m+1}(a_{i−1} − ca_{i})(\overline{a_{i−1}} − \overline{ca_{i}})

= ∑_{i=0}^{m+1}((|a_{i−1}|^{2} + |c|^{2} · |a_{i}|^{2}) − (ca_{i}\overline{a_{i−1}} + \overline{c}\overline{a}_{i}a_{i−1}))

= (1 + |c|^{2}) ∑_{i=0}^{m} |a_{i}|^{2} − ∑_{i=1}^{m}(ca_{i}\overline{a_{i−1}} + \overline{c}\overline{a}_{i} · a_{i−1}).

Similarly, ∥(\overline{c}X − 1) · A(X)∥_{2} can be expanded to give the same expression. Q.E.D.

For any A(X) ∈ [X] whose complex roots are α_{1},…, α_{m} (not necessarily distinct), define the measure of A to be

M(A) = |a| · ∏_{i=1}^{m} max{1, |α_{i}|}

where a is the leading coefficient of A(X). The effect of the max function is simply to discard from the product any root within the unit disc. Measures has the nice property that

A|B implies M(A)/|a| ≤ M(B)/|b|

where a = leadA, b = leadB. The following bounds the measure of a polynomial from above:

Theorem 14 (Landau) For all A(X) ∈ [X], we have

M(A) ≤ ∥A∥_{2}.

Proof. Let α_{1},…, α_{m} ∈ be the set of roots of A where

|α_{1}| ≥ ⋯ ≥ |α_{k}| ≥ 1 > |α_{k+1}| ≥ ⋯ ≥ |α_{m}|

for some k = 0,…, m. Let a = lead(A). By repeated applications of the previous lemma,

∥A∥_{2} = ∥a ∏_{i=1}^{m}(X − α_{i})∥_{2}

= ∥a(\overline{α}_{1}X − 1) ∏_{i=2}^{m}(X − α_{i})∥_{2}
= ⋯
= ∥a ∏_{j=1}^{k}(\overline{α}_{j} X − 1) ∏_{i=k+1}^{m}(X − α_{i})∥_{2}.

The leading coefficient of the last polynomial is

b = a ∏_{j=1}^{k} \overline{α}_{j}

and surely ∥A∥_{2} ≥ |b| = |a| ∏_{j=1}^{k} |α_{j}| = M(A). Q.E.D.

Corollary 15 For A(X) ∈ [X] and α a root of A(X), |α| ≤ ∥A∥_{2}/|a| where a = lead(A).

Theorem 16 (Mignotte) Let A, B ∈ [X], b = lead(B), a = lead(A) and n = deg(B). If B|A then

∥B∥_{1} ≤ |\frac{b}{a}| · 2^{n} · ∥A∥_{2}.

Proof. Let B(X) = ∑_{i=0}^{n} b_{i}X^{i} = b ∏_{i=1}^{n}(X − β_{i}). Then for i = 0,…, n:

|b_{n−i}| = |b| ∑_{1≤j_{1}<···<j_{i}≤n} |β_{j_{1}}β_{j_{2}} … β_{j_{i}}|
≤ ∑_{1≤j_{1}<···<j_{i}≤n} M(B)

= \binom{n}{i}M(B).

Summing over all |b_{i}|’s,

∥B∥_{1} ≤ 2^{n}M(B)
≤ 2^{n} · |\frac{b}{a}| · M(A)
≤ 2^{n} · |\frac{b}{a}| · ∥A∥_{2}.

Q.E.D.

Of course, since ∥B∥_{2} ≤ ∥B∥_{1} (Lecture I.8), we get an upper bound on ∥B∥_{2} as well. If C, B are integer polynomials and C|B then |lead(C)/lead(B)| ≤ 1. Therefore:

Corollary 17 Let A, B, C ∈ Z[X] with C = GCD(A, B). Then

∥C∥_{1} ≤ 2^{n} min{∥A∥_{2}, ∥B∥_{2}}

where deg(A) ≥ deg(B) = n.

Incidentally, the existence of bounds for the coefficient size of factors implies that the problem of factorizing integer polynomials is finite.

The above bounds of Mignotte has been sharpened by Beauzamy [1] by using a certain weighted L_{2}-norm of polynomials.

Exercise 5.1: (Davenport-Trager) Construct examples in which the coefficients of the GCD of A, B ∈ [X] grows much larger than the coefficients of A, B. HINT: A = (X +1)^{2k}(X −1), B = (X + 1)^{2k}(X^{2} − X + 1).

Exercise 5.2: The following bounds are from K. Mahler [Mathematika 7(1960)98-100]. Let F (X) be a complex function, F (0) ≠ 0, ξ_{1},…, ξ_{N} are all the zeroes of F (X) (multiplicities taken into account) satisfying |ξ_{i}| ≤ r for all i, F (X) is regular inside the closed disc |x| ≤ r. Then Jensen’s formula in analytic function theory says

\frac{1}{2π} ∫_{0}^{2π} log |F (re^{iθ})|dθ = log |F (0)| + ∑_{i=1}^{N} log \frac{r}{|ξ_{i}|}.

§6. Modular GCD  Lecture IV  Page 13

(a) Let f(X) = ∑_{i=0}^{n} a_{i}X^{i} ∈ [X], a_{0}a_{n} ≠ 0. Let the roots of f(X) be ξ_{1},…, ξ_{n} such

that

|ξ_{1}| ≤ ⋯ ≤ |ξ_{N}| ≤ 1 < |ξ_{N+1}| ≤ ⋯ ≤ |ξ_{n}|.

Apply Jensen’s formula with r = 1 to show

\frac{1}{2π} ∫_{0}^{2π} log |f(e^{iθ})|dθ = log |a_{0}ξ_{N+1} ⋯ ξ_{n}| = log |M(f)|.

(b) Show

log(2^{−n}∥f∥_{1}) ≤ \frac{1}{2π} ∫_{0}^{2π} log |f(e^{iθ})|dθ ≤ log ∥f∥_{1}.

Hint: The second inequality is immediate, and gives a bound on M(f) weaker than Landau’s.

(c) [Feldman-Mahler] Show for any subset {ξ_{i_{1}},…, ξ_{i_{m}}} of {ξ_{1},…, ξ_{n}},

|a_{0}ξ_{i_{1}} ⋯ ξ_{i_{m}}| ≤ ∥f∥_{1}.

(d) [Gelfond] If f(X) = ∏_{i=1}^{s} f_{i}(X) then

2^{n}∥f∥_{1} ≥ ∏_{i=1}^{s} ∥f_{i}∥_{1}.

§6. A Modular GCD algorithm

We want to compute the GCD of A, B ∈ [X] where

n_{0} = max{deg(A), deg(B)},
N_{0} = max{∥A∥_{2}^{2}, ∥B∥_{2}^{2}}.

The method is essentially due to Collins and Brown.

We have shown that the product of all unlucky primes is ≤ N_{0}^{n_{0}+2}, and that each coefficient of GCD(A, B) has absolute value ≤ 2^{n_{0}}N_{0}. Let

K_{0} = 2 · N_{0}^{n_{0}+2} · 2^{n_{0}}N_{0} = 2^{n_{0}+1}N_{0}^{n_{0}+3}.

Let us compute the list of all initial primes until their product is just ≥ K_{0}. The lucky primes in this list has product at least

K_{0} · N_{0}^{−(n_{0}+2)} = 2^{n_{0}+1}N_{0}.

To identify these lucky primes, we first omit from our list all primes that divide the leading coefficients of A or of B. Among the remaining primes p, we compute A_{p}, B_{p} and then GCD(A_{p}, B_{p}). Let δ(p) be the degree of GCD(A_{p}, B_{p}) and

δ^{∗} = min_{p} δ(p).

Clearly δ^{∗} is the degree of GCD(A, B) since there is a lucky prime p_{0} that remains and this δ(p_{0}) would attain the minimum δ^{∗}. We discard all p where δ(p) > δ^{∗}. We have now identified the set L^{∗} of all lucky primes in our original list. If

GCD(A, B) = ∑_{i=0}^{δ^{∗}} c_{i}X^{i}

we can now find each c_{i} by using the Chinese Remainder Theorem. In more detail, if the coefficient of X^{i} (i = 0,…, δ^{∗}) is c_{i,p} for each p ∈ L^{∗}, then the desired c_{i} is the solution to the system of congruences.

c_{i} ≡ c_{i,p} (mod p), p ∈ L^{∗}.

The correctness of this choice of c_{i} depends on the Luckiness Lemma, and the fact that the product of lucky primes (being at least 2^{n_{0}+1}N_{0}) is at least twice as large as |c_{i}|.

To recapitulate:

1. Compute the list of initial primes whose product is ≥ K_{0}.

2. Omit all those primes that divide lead(A) or lead(B).

3. For each remaining prime p, compute A_{p}, B_{p}, GCD(A_{p}, B_{p}), and δ(p).

4. Find δ^{∗}. Omit remaining unlucky primes.

5. Use Chinese Remainder to reconstruct GCD.

Timing Analysis. Let k_{0} = log K_{0}. Note that the input size can be assumed to be ≥ k_{0} and ≥ n_{0}.

1. This step takes O(k_{0}L(k_{0})).

2. This is negligible compared to other steps.

3(a). To compute A_{p} (similarly for B_{p}) for all p, we exploit the integer evaluation result (lemma 4). Hence all A_{p} can be computed in time O(n_{0}k_{0}L^{2}(k_{0})), the n_{0} coming from the coefficients of A.

3(b). To compute GCD(A_{p}, B_{p}) (for any p) requires

n_{0}L^{2}(n_{0})

operations in _{p}, and each _{p} operation costs O(L^{2}(log p)) = O(log p). Summing over all p’s, we get order of:

n_{0}L^{2}(n_{0}) ∑_{p} log p = n_{0}L^{2}(n_{0}) · k_{0}.

3. Negligible.

§7. What next?  Lecture IV  Page 15

4. Applying the integer interpolation result (lemma 5), we get a time of

O(n_{0}k_{0}L^{2}(k_{0})).

Summing up these costs, we conclude

Theorem 18 The above algorithm computes the GCD of A, B ∈ [X] in time

O(n_{0}k_{0}L^{2}(n_{0} + k_{0})).

If the input A, B has size n, the complexity bound becomes

O(n^{2}L^{2}(n)).

In practice, one could try to rely on luck for lucky primes and this can be the basis of fast probabilistic algorithms.

§7. What else in GCD computation?

There are several further directions in the study of GCD computation:

1. extend to other number fields.

2. extend to multivariate polynomials

3. use randomization techniques to speed up computation

4. develop algorithms that are efficient under the sparse polynomial representation.

We have been assuming the simple GCD problem. The efficient computation of the multiple GCD is still not understood. One such algorithm is the Jacobi-Perron algorithm for multiple GCD for integers. Chung-jen Ho [6,5] has generalized the concept of subresultants to an arbitrary sequence of univariate polynomials, and given a multiple GCD algorithm for F [X]. Another direction is to consider factorization and GCD problems in non-commutative rings. For instance, see [4, chapter 14] for the ring of integer matrices that has a form of unique factorization and GCD. The study of GCD algorithms for quadratic integer rings that are UFD’s is related to the problem of finding shortest vectors in a 2-dimensional lattice. We shall return to the last topic.

References

[1] Bernard Beauzamy. Products of polynomials and a priori estimates for coefficients in polynomial decompositions: a sharp result. Journal of Symbolic Computation, 13:463–472, 1992.

[2] B. Buchberger, G. E. Collins, and R. Loos (eds.). Computer Algebra. Springer-Verlag, 1983.

[3] G. H. Hardy and E. M. Wright. An introduction to the theory of numbers. Oxford University Press, 1959. 4th Edition.

[4] L. K. Hua. Introduction to Number theory. Springer-Verlag, 1982.

[5] Chung jen Ho. Fast parallel gcd algorithms for several polynomials over integral domain. Technical Report 142, NYU-Courant Institute, Robotics Laboratory, 1988.

[6] Chung jen Ho. Topics in algebraic computing: subresultants, GCD, factoring and primary ideal decomposition. PhD thesis, Courant Institute, New York University, June 1989.

[7] Lars Langemyr. Computing the GCD of two polynomials over an algebraic number field. PhD thesis, The Royal Institute of Technology, Stockholm, Sweden, January 1989. Technical Report TRITA-NA-8804.

[8] J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois J. Math., 6:64–94, 1962.