FACTORING POLYNOMIALS OVER GLOBAL FIELDS

KARIM BELABAS, MARK VAN HOEIJ, JÜRGEN KLÜNERS, AND ALLAN STEEL

Abstract. In this paper we prove polynomial time complexity for a now widely used factorization algorithm for polynomials over the rationals. Our approach also yields polynomial time complexity results for bivariate polynomials over a finite field.

Contents

1. Introduction 1 2. Notations 2 3. General description 3 3.1. Linearize 3 3.2. Approximately solve knapsack 3 3.3. Conclude 4 4. The case K = ℚ 5 5. The case K = 𝔽_{q}(t) 8 References 11

1. Introduction

Let K be a global field. The goal of this paper is to present a practical algorithm which factors polynomials f ∈ K[X] in polynomial time, in particular for the cases K = ℚ and K = 𝔽_{q}(t). The seminal Zassenhaus [Zas69] method to factor in K[X] is as follows. We may assume that f is separable. First, compute a bound for the factors of f, then find a non-archimedean place v of K such that the reduction f̄ of f modulo v remains separable in k[X] where k is the residue field of v. Since k is finite we can factor f̄ in k[X] using well known algorithms.

Let K_{v} be the completion of K at v. Let O_{v}, resp. O be the maximal order of K_{v}, resp. K. If K = ℚ then v is a prime number, K_{v} the v-adic numbers, O_{v} the v-adic integers, O = ℤ and k = ℤ/vℤ.

If K = 𝔽_{q}(t) then O = 𝔽_{q}[t] and we will choose a finite place v, which corresponds to choosing an irreducible polynomial v ∈ 𝔽_{q}[t]. If α is a root of this polynomial, then k ≅ 𝔽_{q}(α), O_{v} ≅ k[[t − α]] and K_{v} ≅ k((t − α)), see also Section 5.

After multiplying if necessary f by an element of O, we may assume f ∈ O[X]. By Hensel’s lemma, the factorization of f̄ can be lifted to a factorization

f = ℓ_{f}f_{1} ⋯ f_{r}

in K_{v}[X] where ℓ_{f} ∈ K ⊂ K_{v} is the leading coefficient of f, and f_{1}, …, f_{r} are monic and irreducible in K_{v}[X]. We choose v so that f ∈ O_{v}[X] and ℓ_{f} does not vanish mod v, so f_{1}, …, f_{r} ∈ O_{v}[X]. In actual computations, elements of O_{v} are computed modulo v^{ℓ} for some ℓ > 0 and lifted to O. For a ∈ O_{v} we write “a mod v^{ℓ}” for such a lift of a to O. This notation is extended to O_{v}[X] coefficient-wise. By Hensel lifting the irreducible factors of f̄ we can compute f_{1}, …, f_{r} mod v^{ℓ} for any fixed ℓ > 0.

Second author supported by NSF grant 0098034.

Let g ∈ K[X] be a monic irreducible factor of f. Then

g = f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}}

where e_{i} ∈ {0, 1} for all 1 ≤ i ≤ r. If ℓ is large enough compared to a bound on the coefficients of g, we may test for given e_{1}, …, e_{r} ∈ {0, 1} whether f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}} ∈ K[X] by computing ℓ_{f}f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}} mod v^{ℓ} and checking whether this divides f in K[X]. This time, the lift “… mod v^{ℓ}” to O[X] is not arbitrary. Choosing the right lift is straightforward if K is ℚ or 𝔽_{q}(t) since there are canonical minimal lifts to O, but requires care for general global fields (see [Bel03] for the number field case).

The Zassenhaus algorithm finds the e_{i} by an exhaustive enumeration, which works very well if r is small or the K-rational irreducible factors are plentiful. Otherwise, we face combinatorial explosion and exponential behavior. The landmark paper by Lenstra et al. [LLL82] avoids this combinatorial problem by constructing K-rational factors with lattice basis reduction (LLL-reduction). The original paper assumes K = ℚ, but was suitably generalized by Arjen Lenstra [Len82] (K a number field), then Pohst and Méndez [PO03] (K any global field). Unfortunately, although this algorithm runs in polynomial time, it is rather slow in practice since it requires Hensel lifting to huge accuracy, followed by the LLL-reduction of correspondingly huge lattices. Mark van Hoeij [Hoe02] gave a solution to the combinatorial problem for K = ℚ by reducing it to a knapsack/LLL problem using power sums. Earlier, Sasaki et. al. [SSH93] had already used power sums to solve the combinatorial problem for the bivariate case with linear algebra. The algorithm in [Hoe02] was generalized to number fields by Belabas [Bel03]. These two papers stated no complexity bound. We shall describe a similar approach over a general global field K, and show it runs in polynomial time, although details will only be provided for the cases K = ℚ and K = 𝔽_{q}(t). The key idea in our approach is to use logarithmic derivatives and multiply them by f. This not only simplifies complexity proofs, but has also two algorithmic advantages, see Remark 5.4.

2. Notations

Throughout the paper we will use the following notations: Let K be a global field of characteristic p ≥ 0 with maximal order O. We want to factor a separable polynomial f ∈ K[X] of degree n > 1. After multiplying by an element of K we may assume that f ∈ O[X]. Let v be a non-archimedean place of O. We denote by K_{v} the completion of K at v, with maximal order O_{v}, maximal ideal v and finite residue field k. Let f̄ be the image of f in k[X], and assume that f̄ is still separable. We also assume that the leading coefficient ℓ_{f} ∈ O of f does not vanish mod v, so the degree of f̄ is still n. In the number field case, instead of working with O we can work with a subring of O if the computation of O is too costly, see [Bel03].

We have the factorizations into irreducible elements

f = ℓ_{f}f_{1} ⋯ f_{r} ∈ O_{v}[X], f̄ = ℓ̄_{f} f̄_{1} ⋯ f̄_{r} ∈ k[X], and f = ℓ_{f}g_{1} ⋯ g_{s} ∈ K[X].

Furthermore, ℓ_{f}g_{i} ∈ O[X]. Obviously 1 ≤ s ≤ r ≤ n. We call the f_{i} the local factors and the g_{j} the K-factors.

Fix an integer ℓ ≥ 1. We can not compute f_{i} ∈ O_{v}[X] with infinite accuracy, but we can compute f_{i} mod v^{ℓ}, which is in O[X].

3. General description

Our method relies on two main ideas:

3.1. Linearize. The logarithmic derivative is a group homomorphism from the multiplicative group K_{v}(X)^{∗} to the additive group K_{v}(X), and has kernel K_{v}(X^{p})^{∗}. The first main idea is to multiply this by f. Then we obtain the following group homomorphism:

Φ : K_{v}(X)^{∗}/K_{v}(X^{p})^{∗} → K_{v}(X)
g ↦ fg′/g.

If g is in the subgroup of K_{v}(X)^{∗}/K_{v}(X^{p})^{∗} generated by the local factors f_{i}, then Φ(g) ∈ O_{v}[X]. If g is in the subgroup generated by the K-factors g_{j}, then Φ(g) ∈ O[X]. To see this, take one such g_{j}. Take any prime ideal of O and let w be the corresponding valuation on K, which is extended to a valuation on K[X] by taking w(∑ c_{i}X^{i}) = min_{i} w(c_{i}). Now Φ(g_{j}) is the product of g′_{j} and f/g_{j} and hence in K[X]. Since w(g′_{j}) ≥ w(g_{j}) we get w(Φ(g_{j})) = w(g′_{j} f/g_{j}) ≥ w(g_{j} f/g_{j}) which is ≥ 0 since f ∈ O[X]. So the valuation of Φ(g_{j}) ∈ K[X] is non-negative for any prime ideal of O and hence Φ(g_{j}) ∈ O[X].

Compared to [Hoe02], we have replaced power sums by f times the logarithmic derivative. To show the connection we will define power sums. Let g ∈ K[X] be a monic separable polynomial. The i’th power sum (i’th “trace”) of g is:

Tr_{i}(g) := ∑_{α} α^{i}

where the sum is taken over the roots α of g in an algebraic closure of K. It is known that

g′/g = ∑_{i≥0} Tr_{i}(g)X^{−i−1},

which shows the relation between g′/g and power sums. Despite this relation, our “f times g′/g approach” turns out to be more convenient for complexity proofs than power sums, and also has practical advantages when f is sparse or not monic.

3.2. Approximately solve knapsack. Let G_{v} ⊂ K_{v}(X)^{∗}/K_{v}(X^{p})^{∗} be the subgroup generated by the local factors. Our goal is to find the subgroup G ⊂ G_{v} generated by the irreducible K-factors of f. To do this we first construct the “knapsack lattice” L in a similar way as in [Hoe02], except that instead of traces (power sums) of f_{j} we use the coefficients of Φ(f_{j}), lifted mod v^{ℓ} to O. We then reduce this lattice with LLL if the characteristic is p = 0, and 𝔽_{p}-linear Gaussian elimination if p > 0, for details see Sections 4 and 5. Large basis vectors are then discarded, yielding a sublattice L′ of L, associated to a subgroup G′ of G_{v}. Note that L′ and G′ depend implicitly on ℓ.

3.3. Conclude.

Theorem 3.1. We have G = G′ provided ℓ is large enough.

Proof. We will only sketch the proof, leaving the details to Sections 4 and 5. If G′ is strictly larger than G, then by Lemma 3.2 below, it contains an element, represented by a rational function g ∈ K_{v}(X)^{∗}, g ∉ K_{v}(X^{p})^{∗}, such that

(1) At least one f_{i} divides Φ(g),

(2) None of the \overline{g}_{j} divide \overline{Φ(g)} where the bar indicates reduction to k[X].

(3) H := Φ(g) mod v^{ℓ} is “small”.

Indeed, it is a small perturbation (see Lemma 3.2 below) of a vector in the LLL basis of L′ that is small otherwise it would have been discarded.

The clumsy argument for the third condition is only needed for characteristic p = 0. If p > 0, all elements of L′ are small. Now, let g be as above, H := Φ(g) mod v^{ℓ}, and let R := Res(f, H) be the resultant of f and H. Then

• Res(f, Φ(g)) = 0, hence v^{ℓ} | R. In fact, v^{ℓσ} | R where σ is the sum of the degrees of the f_{i} that divide Φ(g). Item (1) above implies σ > 0.

• R ≠ 0, because if R was zero then H would be divisible by some g_{j}, so \overline{H} would be divisible by \overline{g}_{j}, contradicting item (2) above.

One obtains a contradiction if v^{ℓ} is larger than R. Since R is the determinant of the Sylvester matrix of f and H, one obtains a bound that is polynomial in terms of the sizes of f and H. □

Lemma 3.2. Suppose G ⊊ G′. Then there exists an element g ∈ G′ \ G such that (1) f_{i} | Φ(g) ∈ O_{v}[X] for some 1 ≤ i ≤ r.

(2) \overline{g}_{j} ∤ \overline{Φ(g)} for all 1 ≤ j ≤ s.

Proof. Elements g ∈ G_{v} can be written in the form g = f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}} · K_{v}(X^{p})^{∗} where the integers e_{i} are defined mod p. We view e_{i} as element of ℤ/pℤ, and then define the support of g as Supp g = {i | e_{i} ≠ 0}. Since the f_{i} are pairwise coprime and irreducible in O_{v}[X], we have

f_{i} | Φ(f_{j}) ⟺ i ≠ j.

So f_{i} | Φ(g) iff e_{i} is zero in ℤ/pℤ, and g_{j} | Φ(g) iff Supp g ⋂ Supp g_{j} = ∅.

The supports of g_{1}, …, g_{s} form a partition of {1, …, r}. Choose any element g ∈ G′ \ G. For all 1 ≤ j ≤ s with Supp g_{j} ∩ Supp g = ∅, replace g by g_{j}g. Then condition (2) is satisfied (recall that \overline{f} is separable), and g is still in G′ \ G. Write this g as f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}} · K_{v}(X^{p})^{∗} with e_{i} ∈ ℤ/pℤ. Since g is not in the group G generated by g_{1}, …, g_{s}, there must be some g_{j} for which S_{j} := {e_{i} | i ∈ Supp g_{j}} contains more than one element. Then take an element e ∈ S_{j} and replace g by g/g_{j}^{e}. Now g satisfies both conditions (1) and (2). □

Remark 3.3. Given any g ∈ G′ \ G, the above proof shows that a “small change” suffices to obtain an element of G′ \ G that satisfies conditions (1) and (2).

We have sketched a general proof and omitted the details. Filling in these details is easy for the case K = 𝔽_{q}(t) discussed in Section 5. The details for K = ℚ require more work, which is what we will do in the next section. Note that our f times g′/g approach is similar to Miller’s [Mil92] idempotents approach, but has the advantage that one does not need to multiply by the discriminant.

4. The case K = ℚ

For f ∈ ℂ[X] with leading coefficient ℓ_{f}, let

M(f) := |ℓ_{f}| ∏_{|α|>1} |α|^{m_{α}}

be the Mahler measure of f, where the product is taken over all roots α ∈ ℂ of f with absolute value > 1, and m_{α} is the multiplicity of the root α.

Lemma 4.1. If f, g ∈ ℂ[X] and g | f then

Φ(g) = ∑_{i=0}^{n−1} a_{i}X^{i} ∈ ℂ[X], with |a_{i}| ≤ B_{i} := \binom{n − 1}{i}nM(f).

Proof. We may assume g is not a constant. Then the degree of Φ(g) ∈ ℂ[X] is n − 1. The Mahler measure of Φ(g) is bounded by deg(g)M(f) since M(A′) ≤ deg(A)M(A), see [Mah61], and M(AB) = M(A)M(B) for any A, B ∈ ℂ[X] [MPS99, p. 79]. Bounding deg(g) by n, the upper bound now follows by [MPS99, Lemma 2.1.9]. □

We now restrict to the case K = ℚ (for the additional details needed in the number field case see [Bel03]). Then O = ℤ and v is a prime number. We assume f ∈ ℤ[X] is separable. By equation (3.9) in [LLL82] there exists a “small” prime v such that f remains separable mod v. We use ∥.∥_{2} for the L^{2} norm on ℤ^{n} and on ℤ[X]_{<n}, which denotes the set of polynomials in ℤ[X] of degree < n.

Corollary 4.2. With f ∈ ℤ[X] and g any factor of f in ℚ[X], we have Φ(g) ∈ ℤ[X]_{<n} and

∥Φ(g)∥_{2} ≤ B(f) := 2^{n−1}n ∥f∥_{2} .

Proof. That Φ(g) is in ℤ[X] was proved in Section 3.1. Using Lemmata 2.1.8 and 2.1.9 in [MPS99] we get that ∥Φ(g)∥_{2} ≤ 2^{n−1}M(Φ(g)). As in the proof of Lemma 4.1 we get that 2^{n−1}M(Φ(g)) ≤ 2^{n−1}nM(f). Corollary 2.1.5 in [MPS99] states that M(h) ≤ ∥h∥_{2} for all non constant polynomials h which finishes the proof. □

For 1 ≤ j ≤ s write the monic irreducible K-factors as g_{j} = f_{1}^{w_{j,1}} ⋯ f_{r}^{w_{j,r}} with w_{j,1}, …, w_{j,r} ∈ {0, 1} and write w_{j} := (w_{j,1}, …, w_{j,r})^{tr} ∈ ℤ^{r} where tr denotes the transpose. Denote W = ℤw_{1} + ⋯ + ℤw_{s}.

If we have any basis u_{1}, …, u_{s} of W then we can find {w_{1}, …, w_{s}} by computing the reduced echelon form of u_{1}, …, u_{s}, or by using the following shortcut: write {1, …, r} as a disjoint union of subsets in such a way that i, j are in the same subset iff the i’th and j’th entry of u are the same for every u in u_{1}, …, u_{s}.

Let I_{r} be the r by r identity matrix. Fix some integer ℓ ≥ 1. Recall that “mod v^{ℓ}” denotes the canonical minimal lift to ℤ. Let the a_{i,j} ∈ ℤ be the coefficients of Φ(f_{j}) mod v^{ℓ}, so

Φ(f_{j}) mod v^{ℓ} = ∑_{i=0}^{n−1} a_{i,j}x^{i} (1 ≤ j ≤ r).

Then let the all-coefficients lattice L be the column space of the following matrix:

A := (\begin{matrix}I_{r} & 0 \\ A_{1} & v^{ℓ}I_{n} \end{matrix}) , where A_{1} := (\begin{matrix}a_{0,1} & ⋯ & a_{0,r} \\ ⋮ & ... & ⋮ \\ a_{n−1,1} & ⋯ & a_{n−1,r} \end{matrix}) .

Note that L depends on ℓ. For e = (e_{1}, …, e_{r+n})^{tr} ∈ L we denote the corresponding element Φ(f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}}) of Φ(G_{v}) as POL(e). Each K-factor g_{j} corresponds to a vector in L we denote by w̃_{j}, whose entries come from w_{j} and Φ(g_{j}). Then \left∥{ \atop w̃_{j}}\right∥_{2} ≤

\sqrt{∥w_{j}∥_{2}^{2} + B^{2}} ≤ B′ := \sqrt{r^{2} + B^{2}} where B = B(f) is as in Corollary 4.2.

Theorem 4.3. Let f ∈ ℤ[X] separable and B′ as above. Let b_{1}, …, b_{n} an LLLreduced basis for the all-coefficients lattice L, let b_{1}^{∗}, …, b_{n}^{∗} the associated Gram-Schmidt orthogonalized basis, and let t the smallest index such that ∥b_{j}^{∗}∥_{2} > B′ for all j > t. Let L′ := ℤb_{1} + ⋯ + ℤb_{t}. If

(1)  v^{ℓ/n} > ∥f∥_{2} (2^{n−1} + n)B′(1 + B′).

then the projection of L′ on the first r entries is W.

Proof. It follows from the proof of (1.11) in [LLL82] that every w ∈ L with ∥w∥_{2} ≤ B′ is in L′. So w̃_{1}, …, w̃_{s} ∈ L′ and hence the projection of L′ on the first r entries contains W. Assume it is strictly larger, then POL(b_{u}) ∉ Φ(G) for some 1 ≤ u ≤ t. From the properties of LLL-reduced bases, ∥b_{u}∥_{2} ≤ γ^{t−1}B′, where γ > 4/3 is a number that can be chosen in the LLL-reduction algorithm (one may set γ := 2 as in the original LLL paper). More precisely, ∥b_{u}^{∗}∥_{2} ≤ γ^{t−u} ∥b_{t}^{∗}∥_{2} and ∥b_{u}∥_{2} ≤ γ^{u−1} ∥b_{u}^{∗}∥_{2} for all u ≤ t ≤ n.

Using Lemma 3.2 as in the proof of Theorem 3.1 one can show that there exists a vector g ∈ L′ such that f_{i} | POL(g) for some 1 ≤ i ≤ r, and v^{ℓ} | Res(f, H) ≠ 0, where H := POL(g) mod v^{ℓ}. From the proof of Lemma 3.2, this vector g may be obtained by first adding a subset of {w̃_{1}, …, w̃_{s}} to b_{u}, yielding a vector b such that

∥b∥_{2} ≤ (γ^{t−1} + s)B′,

and then by adding to b a vector of the form ew̃_{i} for some integer e with |e| ≤ |b|_{∞} ≤ ∥b∥_{2}. Hence

∥H∥_{2} ≤ ∥g∥_{2} ≤ (γ^{t−1} + s)B′(1 + B′).

From the preceding discussion and Hadamard’s bound on determinants,

v^{ℓ} ≤ |Res(f, H)| ≤ ∥f∥_{2}^{deg H} ∥H∥_{2}^{n} ,

and we may bound deg H, s, t ≤ n to derive a contradiction with (1). □

From this theorem, we obtain ℓ log v = O(n^{2} + n log ∥f∥_{2}). Since Hensel lifting and LLL-reduction are polynomial time algorithms, we see that W can be computed in polynomial time. Our estimate for ℓ log v is the same as in the proof of Proposition 3.4 in [LLL82] (one needs to add log v if v is not small but we ignore this issue) and is worse than [Mil92], so we do not obtain a new complexity result.

Although there is no practical reason for doing so (since power sums do not offer advantages over coefficients of Φ), one could now use the relation between power sums (called traces in [Hoe02]) and Φ to show the algorithm in [Hoe02] is polynomial time provided that one uses what we call the all-traces version of the algorithm. This version uses all of the traces numbered 1, …, n − 1 at the same time, so the LLL-reduction takes place in ℤ^{r+n−1}.

From a practical point of view, the all-traces and all-coefficients versions are slow and thus not interesting. The main question in this paper is whether practical versions of the algorithm run in polynomial time. Using one trace at a time works very well in practice, see [Bel03]. We will show that the “one coefficient at a time” version factors in ℚ[X] in polynomial time (the same must then also be true for one trace at a time).

Let B_{i} be the bound for |a_{i}| given in Lemma 4.1. For 0 ≤ i ≤ n − 1 and g ∈ K_{v}(X)^{∗} write T′_{i}(g) ∈ ℤ the coefficient of X^{i} in Φ(g) mod v^{ℓ}. Let T_{i}(g) := T′_{i}(g)/B_{i} ∈ ℚ. Note that T_{i} depends on ℓ, which is a fixed integer ≥ 1 that may be chosen arbitrarily. Lemma 4.1 says that if g is a K-factor of f, then |T_{i}(g)| ≤ 1.

Proposition 4.4. One can compute a sequence of lattices L_{n−1}, L_{n−2}, …, L_{0} with the following properties:

(1) ℤ^{r} = L_{n−1} ⊇ L_{n−2} ⋯ ⊇ L_{0} ⊇ W

(2) L_{i} = ℤb_{i,1} + ⋯ + ℤb_{i,r_{i}} for some integer r_{i} and some vectors b_{i,j} ∈ ℤ^{r} with the following properties:

(a) ∥b_{i,j}∥_{2} ≤ (r + 2)γ^{r}.

(b) If b_{i,j} = (e_{1}, …, e_{r})^{tr} then T_{i}(f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}}) ≤ (r + 2)γ^{r} where γ > 4/3 is a number that can be chosen in the LLL-reduction algorithm.

Proof. If i = n − 1 we may take b_{i,1}, …, b_{i,r_{i}} as the standard basis of ℤ^{r}. If i < n − 1 then we may assume that L_{i+1} = ℤb_{i+1,1} + ⋯ + ℤb_{i+1,r_{i+1}} has been computed and define b′_{j} as follows: First write b_{i+1,j} = (e_{1}, …, e_{r})^{tr}, then compute a := e_{1}T_{i}(f_{1}) + ⋯ + e_{r}T_{i}(f_{r}) and set b′_{j} := (e_{1}, …, e_{r}, a)^{tr} ∈ ℤ^{r} × ℚ. Now let L′ := ℤb′_{1} + ⋯ + ℤb′_{r_{i+1}} + ℤP where P = (0, …, 0, v^{ℓ}/B_{i})^{tr}. Let b_{1}, b_{2}, … be an LLL-reduced basis of L′, let b_{1}^{∗}, b_{2}^{∗}, … the associated orthogonalized basis, and let r_{i} be the smallest index such that ∥b_{j}^{∗}∥_{2} > r + 2 for all j > r_{i}. Now define b_{i,j} as the projection of b_{j} on the first r entries and let L_{i} := ℤb_{i,1} + ⋯ + ℤb_{i,r_{i}}.

Consider the vector w_{j} corresponding to the K-factor g_{j} and let w′_{j} be the corresponding vector in L′. The first r entries of w′_{j} are in {0, 1}, and the last entry equals T_{i}(g_{j}) ∈ ℚ which has absolute value ≤ 1 by Lemma 4.1. Hence, ∥w′_{j}∥_{2} ≤ \sqrt{r + 1} < r + 2. Then it follows from the proof of (1.11) in [LLL82] that w_{j} ∈ L_{i} and hence W ⊆ L_{i}. By the properties of an LLL-reduced basis, we have ∥b_{j}∥_{2} ≤ (r + 2)γ^{r} when j ≤ r_{i} which implies (2a) resp. (2b) since projecting on the first r entries resp. last entry does not make a vector longer.

The lattice L′ to be reduced was in ℤ^{r} × ℚ. Lattice reduction in ℤ^{r+1} is more efficient, so we round each of the numbers T_{i}(f_{1}), …, T_{i}(f_{r}), v^{ℓ}/B_{i} to the nearest integer. Then we obtain a lattice L′ ⊆ ℤ^{r+1} but now we have introduced rounding errors. Consider again the vectors w_{j} ∈ W and w′_{j} ∈ L′. If w_{j} has σ entries equal to 1, then the last entry of w′_{j} is the sum of σ elements of {T_{i}(f_{1}), …, T_{i}(f_{r})} plus an integer in the interval (−σ/2, σ/2) times v^{ℓ}/B_{i}. We introduced an error ≤ 0.5 in each of the numbers T_{i}(f_{1}), …, T_{i}(f_{r}), v^{ℓ}/B_{i}. Then the total rounding error in the last entry of w′_{j} is less than 0.5(σ + σ/2) which is less than r, so this entry will have absolute value < r + 1. Then ∥w′_{j}∥_{2} < \sqrt{σ + (r + 1)^{2}} < r + 2. The proposition is stated with r +2 instead of \sqrt{r + 1} so that the bounds can still be used for practical implementations that round T_{i}(f_{1}), …, T_{i}(f_{r}), v^{ℓ}/B_{i} to ℤ. □

Lemma 4.5. With the notations of Proposition 4.4, the following holds for every n − 1 ≥ i ≥ i′ ≥ 0. If e = (e_{1}, …, e_{r})^{tr} is an element of {b_{i′,1}, …, b_{i′,r_{i′}} } then

T_{i}(f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}}) ≤ 2^{O(r^{2})}

Proof. The entries of the b_{i,j} and e are bounded by (r + 2)γ^{r} = 2^{O(r)}. Since e ∈ L_{i′} ⊆ L_{i} we can write e = ∑_{j=1}^{r_{i}} c_{j}b_{i,j} for some c_{j} ∈ ℤ that can be found by solving linear equations. With Cramer’s rule one finds |c_{j}| ≤ 2^{O(r^{2})}. Multiplying this by r_{i} and by the bound in Proposition 4.4 part (2b) leads to the bound 2^{O(r^{2})}. □

Theorem 4.6. L_{0} = W for some ℓ polynomially bounded in terms of n and log ∥f∥_{2}.

Proof. If L_{0} ≠ W then let e be one of the vectors b_{0,j} from Proposition 4.4 that is not in W. Write e = (e_{1}, …, e_{r})^{tr} and g = f_{1}^{e_{1}} ⋯ f_{r}^{e_{r}}. Write Φ(g) = ∑ c_{i}X^{i}. Then the corresponding vector in the all-coefficients lattice (see Theorem 4.3) is ẽ:= (e_{1}, …, e_{r}, c_{0}, …, c_{n−1})^{tr} where c_{0}, …, c_{n−1} are bounded in absolute value by 2^{O(r^{2})} by Lemma 4.5. Applying the process in the proof of Lemma 3.2 we obtain a new vector e′ whose length differs at most (s + max{e_{1}, …, e_{r}})B′ from e. The last n entries of this vector are the coefficients of a polynomial H ∈ ℤ[X]_{<n} and we have v^{ℓ} | Res(f, H) ≠ 0 in the same way as in Theorem 4.3. This implies that log v^{ℓ} is polynomially bounded. □

We propose to implement the “one coefficient at a time” approach in the following way: start with a value for ℓ that is at most as large as what one would use in the Zassenhaus approach. Then, compute L_{n−1}, L_{n−2}, … until we find W. If we reach L_{0} and we still have not found W then we must increase ℓ. The computation of each L_{i} should be done using the incremental strategy of Section 2.4 in [Bel03], reducing one large-determinant LLL-reduction to a sequence of smaller LLL-reductions that at the end produce the same result. Then one has a polynomial time algorithm that runs very well in practice, with running times that should be the same as those reported in [Bel03] for ℚ[X].

The incremental strategy from [Bel03] is very efficient because after each LLLreduction one can check if vectors can be removed. This way, there will be no long vectors in the input of the next LLL-reduction. In fact, one can keep the bit-length of these vectors below a bound that depends solely on r. This means that the cost of each individual call to the LLL-reduction algorithm can be bounded by a polynomial that depends only on r and is independent of both n and ∥f∥_{2}, which explains why the algorithm performs so well in practice. Unfortunately, Lemma 4.5 leads to a rather pessimistic bound on the number of calls to the LLL-reduction algorithm.

5. The case K = 𝔽_{q}(t)

Now p > 0, q is a power of p, O = 𝔽_{q}[t], and the place v corresponds to an irreducible polynomial in 𝔽_{q}[t], which we shall also denote as v. Let f ∈ O[X]. We want to factor f, viewed as element of 𝔽_{q}(t)[X]. We assume that f is separable. Denote α as a root of v ∈ 𝔽_{q}[t], then the residue field k = 𝔽_{q}[t]/(v) is isomorphic to 𝔽_{q}(α). We choose v in such a way that f̄, the image of f in k[X], remains separable, and still has degree n. We get the factorization

f̄ = ℓ̄_{f} f̄_{1} ⋯ f̄_{r} ∈ k[X].

Representing t − α with a new variable t̃, the map t ↦ t̃+ α is an isomorphism from 𝔽_{q}[t]/(v^{ℓ}) to 𝔽_{q}(α)[t̃]/(t̃^{ℓ}). Taking limits, one finds an isomorphism from

O_{v} = lim_{←} 𝔽_{q}[t]/(v^{ℓ})

to

𝔽_{q}(α)[[t̃]] = lim_{←} 𝔽_{q}(α)[t̃]/(t̃^{ℓ}).

By Hensel’s lemma, we get a factorization

f = ℓ_{f}f_{1} ⋯ f_{r} ∈ O_{v}[X].

If g ∈ O_{v}[X] we denote “g mod v^{ℓ}” as the unique lift of g to 𝔽_{q}[t, X] whose deg_{t} is smaller than deg_{t}(v^{ℓ}) where deg_{t} denotes the degree with respect to t. We can not compute f_{i} ∈ O_{v} with infinite accuracy, however, for any integer ℓ > 0 we can compute f_{i} mod v^{ℓ}, which is an element of 𝔽_{q}[t, X].

Note that the above technicalities with O_{v} become easier if we take v = t so that t̃ = t. However, we can not always do this, we can only take v = t if f(t = 0, X) is separable and has degree n (it is possible that this situation is unreachable with 𝔽_{q}-linear transformations).

Lemma 5.1. Let B_{i} := deg_{t}(f) (we write B_{i} instead of B because another bound that does depend on i will be given in Lemma 5.8). Let g ∈ 𝔽_{q}[t][X] be a polynomial which divides f then

Φ(g) = ∑_{i=0}^{n−1} a_{i}(t)X^{i} ∈ 𝔽_{q}[t][X] with deg_{t}(a_{i}) ≤ B_{i}.

Proof. From Φ(g) = fg′/g we get deg_{t}(Φ(g)) + deg_{t}(g) = deg_{t}(g′) + deg_{t}(f). Since deg_{t}(g′) ≤ deg_{t}(g) we get the wanted bound. □

The idea is as follows. Let g ∈ G_{v}. If the degree of one of the coefficients of Φ(g) mod v^{ℓ} exceeds the degree bound B_{i} then g is not a K-factor of f. We use this to replace the Zassenhaus combinatorial search by linear algebra.

As in the rational case we introduce the lattice W ⊆ (ℤ/pℤ)^{r} generated by the exponent vectors of the monic irreducible factors g_{1}, …, g_{s} of f in 𝔽_{q}(t)[X]. Let L be some subspace of (ℤ/pℤ)^{r} that contains W. We start with L = (ℤ/pℤ)^{r}. Our goal is to compute a subspace L′ ⊆ L which still contains W. Let m_{i} = B_{i} + 1 and σ = deg_{t}(v^{ℓ}). Write

Φ(f_{j}) mod v^{ℓ} = ∑_{i=0}^{n−1} a_{i,j}X^{i} (1 ≤ j ≤ r)

so the a_{i,j} are in 𝔽_{q}[t] and have degree < σ. Define

ϕ_{m_{i}}(c_{0}t^{0} + ⋯ + c_{σ−1}t^{σ−1}) := (c_{m_{i}}, …, c_{σ−1})^{tr}

and

A_{i} := (ϕ_{m_{i}}(a_{i,1}) ⋯ ϕ_{m_{i}}(a_{i,r}))

which is an (σ − m_{i}) × r matrix with entries in 𝔽_{q}, and A_{i}e = 0 for all e ∈ W. Now L and W are subspaces of 𝔽_{p}^{r} and A_{i} is defined over 𝔽_{q}. For q = p^{w} write 𝔽_{q} = 𝔽_{p}γ_{1} + ⋯ + 𝔽_{p}γ_{w} and define

(2)  ψ : 𝔽_{q} → 𝔽_{p}^{w}, ∑_{l=1}^{w} c_{l}γ_{l} ↦ (c_{1}, …, c_{w})^{tr},

where tr denotes the transpose. We define Ã_{i} as follows: replace every entry c of A_{i} by ψ(c). Since ψ(c) is a column vector (because of the transpose in its definition) with w entries we see that Ã_{i} is a w(σ − m_{i}) × r matrix with entries in 𝔽_{p}. We still have Ã_{i}e = 0 for all e ∈ W. Now let L′ be the intersection of the kernels of Ã_{0}, …, Ã_{n−1}. Then L′ contains W.

Let B be a degree bound for the resultant R in the proof of Theorem 3.1. Looking at the Sylvester matrix, the estimate from Lemma 5.1 gives B = (2n − 1) deg_{t}(f). Following Theorem 3.1 one finds that L′ must be W when deg_{t}(v^{ℓ}) > B. This proves

Theorem 5.2. If deg_{t}(v^{ℓ}) > (2n − 1) deg_{t}(f) and L′ is the intersection of the kernels of Ã_{i}, i = 0, …, n − 1 then L′ = W. This leads to an algorithm that factors a separable polynomial f ∈ 𝔽_{q}[t][X] in polynomial time.

Remark 5.3. If the total degree of f as bivariate polynomial is n (which denotes the degree of f in X) then one can replace B_{i} from Lemma 5.1 by B_{i} := n − 1 − i. The proof is the same, except that deg_{t} is replaced by the total degree. Then we can replace (2n − 1) deg_{t}(f) by n(n − 1) in the above theorem.

Remark 5.4. If the total degree is n, then our “f times g′/g” approach is equivalent to the power sums approach if we use the bound in Remark 5.3. However, if we use the sharper bound in Lemma 5.8 below, then the two approaches are no longer equivalent. For example, if 𝔽_{q} = 𝔽_{41}, f = X^{10} + t^{2}X^{8} + tX^{5} + 1 and v = t then ℓ = 3 suffices to prove irreducibility with our approach. With power sums it would be ℓ = 6. In the non-monic case (see Example 5.7) our approach has an additional advantage, namely that a reduction to the monic case (which may increase the size of f) is not needed.

Remark 5.5. Replacing a matrix over 𝔽_{q} with a matrix over 𝔽_{p} using the trick in Equation (2) reduces the cost of the linear algebra, but can also reduce the amount of Hensel lifting that is needed. In fact, without it, the bound in Remark 5.3 would actually be sharp! To illustrate this, take a positive integer a, a prime number p, let n := p^{a} + 1, take 𝔽_{q} as the splitting field of X^{n} − 1 over 𝔽_{p}, set f := X^{n} + t^{n} − 1 and v := t. In this example, the intersection of the kernels of the A_{i}, which is what one would calculate without the trick, equals W ⊗ 𝔽_{q} iff ℓ > n(n − 1). With the trick one obtains W iff ℓ > n.

Remark 5.6. In [BLSSW04] the authors followed our f times g′/g approach found in a previous version of this paper and were able to improve the quadratic bound n(n − 1) to a linear bound when p > n(n − 1). It remains an open problem to decide if there is a linear bound for small p (assuming one uses Equation (2)).

In an implementation, one should start with a small value for ℓ, increasing ℓ as long as L′ is not W. To minimize the ℓ at which one reaches W, replace the bounds B_{i} from Lemma 5.1 or Remark 5.3 by the bound given in the Lemma 5.8 below, which is always at least as good but can be better, particularly when f is sparse.

Example 5.7. If 𝔽_{q} = 𝔽_{13}, f = (t^{10} − 1)X^{10} + tX^{2} + 1 and v = t, our algorithm would factor f mod t, Hensel lift to ℓ = 4 and then stop because when ℓ reaches 4, dim(L′) becomes 1, which implies that f is irreducible.

For irreducible f, one often reaches dim(L′)=1 for a small value of ℓ, so an irreducible polynomial could take much less time than a reducible polynomial.

Denote N(f) ⊂ ℝ^{2} as the Newton polygon of f, which is defined as the convex hull of all points (i, j) for which the coefficient of t^{i}X^{j} in f is non-zero. If S_{1}, S_{2} ⊂ ℝ^{2} then define S_{1} + S_{2} := {s_{1} + s_{2} | s_{1} ∈ S_{1}, s_{2} ∈ S_{2}}.

Lemma 5.8. Let B_{i} := sup{m ∈ ℕ | (m, i + 1) ∈ N(f)}. Let g ∈ 𝔽_{q}[t][X] be a polynomial which divides f then

Φ(g) = ∑_{i=0}^{n−1} a_{i}(t)X^{i} ∈ 𝔽_{q}[t][X] with deg(a_{i}) ≤ B_{i}.

Proof. It is well known that N(gh) = N(g) + N(h) for all g, h ∈ 𝔽_{q}[t, X]. It is also clear that N(g′) ⊆ N(g) + {(0, −1)}. Then N(Φ(g)) = N(f/g · g′) = N(f/g) + N(g′) ⊆ N(f/g) + N(g) + {(0, −1)} = N(f) + {(0, −1)}. If (m, i) ∈ N(Φ(g)) then (m, i) ∈ N(f) + {(0, −1)} and hence (m, i + 1) ∈ N(f). □

Remark 5.9. If one chooses a place v of higher degree than necessary, then a smaller ℓ will suffice to reach the same deg_{t}(v^{ℓ}). For small q and reducible f this often reduced the running time in our implementation in Magma. A significant drawback is the increase in cost of factoring \overline{f}. The advantage disappears for very high degrees where one switches to asymptotically fast polynomial arithmetic.

References

[Bel03] K. Belabas A relative van Hoeij algorithm over number fields, Journal of Symbolic

         Computation, to appear. Cf. http://www.math.u-psud.fr/~belabas/pub/#vanhoeij

[BLSSW04] A. Bostan, G. Lecerf, B. Salvy, É. Schost, and B. Wiebelt. Complexity issues in bivariate polynomial factorization, Proceedings of ISSAC, (2004).

[Hoe02] M. van Hoeij, Factoring polynomials and the knapsack problem, J. Number Theory, 95 (2002), pp. 167–189.

[Len82] A. K. Lenstra, Lattices and factorization of polynomials over algebraic number fields, (Berlin), LNCS, vol. 144, Springer, Berlin, (1982), pp. 32–39.

[LLL82] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, pp. 515–534.

[MPS99] M. Mignotte, L. Pasteur, and D. Stefanescu, Polynomials: An Algorithmic Approach, Springer, (1999).

[Mah61] K. Mahler, On the zeros of the derivative of a polynomial, Proc. Roy. Soc. Ser. A, 264 (1961), pp. 145–154.

[Mil92] V. Miller, Factoring Polynomials via Relation-Finding, ISTCS ’92, Springer Lecture Notes in Computer Science 601 (1992), pp. 115–121.

[PZ89] M. E. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Cambridge University Press, (1989).

[PO03] M. E. Pohst and J. Méndez, Factoring polynomials over global fields, preprint.

[SSH93] T. Sasaki, T. Saito and T. Hilano, A unified method for multivariate polynomial factorization, Japan J. Industrial and Applied Math 10, 1 (1993), pp. 21–39.

[Zas69] H. Zassenhaus, On Hensel factorization I, Journal of Number Theory (1969), pp. 291– 311.

Université Paris-Sud, Département de Mathématique, 91400 Orsay, France.

   E-mail address: Karim.Belabas@math.u-psud.fr

Florida State University, 211 Love building, Tallahassee, Florida 32306-3027, USA

   E-mail address: hoeij@zeno.math.fsu.edu

Universität Kassel, Fachbereich Mathematik/Informatik, Heinrich-Plett-Str. 40, 34132 Kassel, Germany.

   E-mail address: klueners@mathematik.uni-kassel.de

School of Mathematics and Statistics F07, University of Sydney NSW 2006, Australia

   E-mail address: allan@maths.usyd.edu.au