Factoring polynomials and 0–1 vectors

Mark van Hoeij Department of Mathematics Florida State University Tallahassee, FL 32306-3027 hoeij@math.fsu.edu

Abstract

A summary is given of an algorithm, published in [4], that uses lattice reduction to handle the combinatorial problem in the factoring algorithm of Zassenhaus. Contrary to Lenstra, Lenstra and Lovász, the lattice reduction is not used to calculate coefficients of a factor but is only used to solve the combinatorial problem, which is a problem with much smaller coefficients and dimension. The factors are then constructed efficiently in the same way as in Zassenhaus’ algorithm.

1 Comparison of three factoring algorithms

Let f ∈ Q[x] be a polynomial of degree N. Write f = ∑_{i=0}^{N} a_{i}x^{i} with a_{i} ∈ Q. Suppose that f is monic (i.e. a_{N} = 1) and square-free (i.e. gcd(f, f′) = 1). Assume that the coefficients a_{i} do not have more than D digits.

Let p be a prime number and let Q_{p} be the field of p-adic numbers. Let f = ∏_{i=1}^{n} f_{i} where f_{i} ∈ Q_{p}[x] are the monic irreducible factors of f in Q_{p}[x]. Let v be a 0–1 vector, i.e. v = (v_{1} … v_{n}) ∈ {0, 1}^{n}. Let g_{v} = ∏ f_{i}^{v_{i}}. Then

{g_{v}|v ∈ {0, 1}^{n}}

is the set of all monic factors of f in Q_{p}[x]. Let

V = {v ∈ {0, 1}^{n}|g_{v} ∈ Q[x]}

so {g_{v}|v ∈ V } is the set of all monic factors of f in Q[x]. Let

B = {v ∈ V |g_{v} irreducible in Q[x]}.

Because Q[x] has unique factorization it follows that V is the set of all {0, 1}-linear combinations of B.

The algorithm of Zassenhaus [1] to factor f in Q[x] works as follows. First the f_{i} are computed modulo a power of p using Hensel lifting. The computation time is bounded by P_{Z}(N, D) which is a polynomial in N and D. Then, for v ∈ {0, 1}^{n}, a method is given to decide if g_{v} ∈ Q[x] or not, and if so, to calculate g_{v} ∈ Q[x]. If g_{v} is not in Q[x], then the time c to verity that is very small, and is almost independent of N, D. For all practical purposes we can assume that this cost c is constant. Calculating g_{v} for all v ∈ B gives the set of all irreducible factors of f. But no method is given to calculate the set B, other than to try all v. Denote |v| = ∑ v_{i}, so g_{v} is a product of |v| p-adic factors. First one tries all v with |v| = 1, then |v| = 2, etc. Whenever a g_{v} ∈ Q[x] is found, the corresponding f_{i} are removed, and n decreases. The complexity depends on M = max{|v|, v ∈ B}. The worst case is M = n, i.e. f is irreducible, because then all 2^{n} vectors v will be be tried (or 2^{n−1} vectors, by skipping the complements of the v’s that were already tried). So the total cost is at most: P_{Z}(N, D) + c2^{n−1} where c is a very small constant. If M = n/2 then the cost is essentially the same. If M < n/2 then the cost is lower, we can bound the cost by P_{Z}(N, D) + cE_{Z}(n, M) where E_{Z}(n, M) ≤ 2^{n−1} depends exponentially on M. After trying all |v| ≤ 3, which can be done quickly, we may assume that M > 3 (if there are still any f_{i} left).

In most examples (even with large N) the number M will be small. Then P_{Z} dominates the computation time and the algorithm works fast. However, in some examples M can be large, in which case cE_{Z} can dominate the computation time. This happens when f has few factors in Q[x] but many factors in Q_{p}[x] for every p. Such polynomials have a very special Galois group; order(σ) << N for every σ in the Galois group. Extreme examples are the Swinnerton-Dyer polynomials, where order(σ) ≤ 2 for all σ. Other examples are resolvent polynomials, which tend to be polynomials of high degree with small Galois groups. For these polynomials, the computation time is dominated by cE_{Z}, and the algorithm of Zassenhaus will be exponentially slow.

The first polynomial time algorithm was given by Lenstra, Lenstra and Lovász. In their paper [2] they give a lattice reduction algorithm (the LLL algorithm). Many combinatorial problems can be solved in polynomial time with LLL by encoding the solutions of the problem as short vectors in a lattice. The LLL algorithm can find the set S of short vectors, provided that all vectors outside of span(S) are sufficiently long in comparison.

In [2] the LLL algorithm is used in the following way. Take one factor f_{1} ∈ Q_{p}[x] of f. The problem to be solved with LLL is: Find, if it exists, a non-zero g ∈ Q[x] of degree < N such that f_{1} divides g. If such g exists, then gcd(f, g) ∈ Q[x] is a non-trivial factor of f. This problem is reduced to lattice reduction as follows. First calculate f_{1} modulo a sufficiently high power of p by Hensel lifting. The cost of Hensel lifting can be bounded by P_{L_{1}}(N, D) which is a polynomial in N, D. From that, a lattice can be constructed that (if f is reducible) contains a vector U_{g} whose entries are the coefficients of g. Then the LLL algorithm can find this vector in a time bounded by P_{L_{2}}(N, D) which is also a polynomial in N and D. So the total computation time is bounded by P_{L} = P_{L_{1}} + P_{L_{2}}, which is a polynomial in N, D. However, P_{L_{1}} > P_{Z} because one must Hensel lift up to a substantially higher power of p. Furthermore, P_{L_{2}} >> P_{Z}, in other words, the algorithm of Zassenhaus is much faster, except when cE_{Z} >> P_{Z} which only happens for polynomials with special Galois groups.

So, there exists a polynomial time algorithm [2], and an exponential time algorithm [1] that is faster most of the time (except when M is large). How can the advantages of both algorithms be combined?

Suppose that g_{v} ∈ Q[x]. The algorithm in [2] would find such g = g_{v} by computing a vector U_{g} in an N-dimensional lattice whose entries are the coefficients of g. Suppose that g is large (say degree five hundred and coefficients with thousands of digits). Lattice reduction is a very general method that can be applied to solve many combinatorial problems. So it is to be expected that if it is used to construct a large expression such as U_{g} that it will take a long time. To have a faster computation, we must use LLL to construct smaller vectors instead.

The vectors in B are much smaller than the vector U_{g}, in two ways. The entries have only 1 digit whereas the entries of U_{g} can have many digits. And the number of entries is only n, usually n is much smaller than N (except for Swinnerton-Dyer polynomials where n = N/2, which is smaller but not much smaller than N).

Because of the much smaller size, LLL can calculate the elements of B much faster than the vector U_{g}. We need to design an input lattice for LLL in such a way, that span(B) and hence B can be obtained from the short vectors found by LLL. To keep the LLL cost to a minimum, we must make sure that the short vectors found by LLL do not contain any information (other than the set B) about the coefficients of a factor g, so that the LLL cost will not depend on the size of g. The LLL cost will then be bounded by a polynomial P (n) that depends only on n, and not on N or D. The cost cE_{Z}(n, M) of finding the set B in Zassenhaus’ algorithm is now replaced by P (n), and the total cost of factoring is now: P_{Z}(N, D) + P (n). So the resulting algorithm is faster than Zassenhaus’ algorithm whenever P (n) < cE_{Z}(n, M). It turns out in experiments that the cut-off point is low. That means that when P (n) is not smaller than cE_{Z}(n, M), then P (n) and cE_{Z}(n, M) are both small, so then the computation time is close to P_{Z}(N, D) for both algorithms. However, when n is larger, then P (n) can be much smaller than cE_{Z}(n, M). Experiments show that polynomials with n > 400, N, D > 2000 can be handled, which is far beyond the reach of [1, 2].

2 How to construct the lattice to find B?

To find linear conditions on v we can not use the coefficients of the polynomial g_{v}, because they do not depend linearly on v, g_{u+v} = g_{u}g_{v}. In order to find linear conditions, a vector T_{A}(g) with s entries (s will be small compared to n) will be defined, that has the following property: T_{A}(g_{1}g_{2}) = T_{A}(g_{1}) + T_{A}(g_{2}) ∈ Q_{p}^{s} for all non-zero g_{1}, g_{2} ∈ Q_{p}[x]. This T_{A}(g) will be constructed in such a way that the entries of T_{A}(g_{v}) are p-adic integers for all 0–1 vectors v, and if furthermore g_{v} ∈ Q[x] then the entries are integers, bounded in absolute value by \frac{1}{2}p^{b} for some integer b.

Now T_{A}(g_{v}) = ∑ v_{i}T_{A}(f_{i}) is a linear combination of the T_{A}(f_{i}), and when g_{v} ∈ Q[x] then the entries of this linear combination are integers. However, the entries of T_{A}(f_{i}) are not yet suitable for use in the LLL input vectors for two reasons. First, these entries of T_{A}(f_{i}) are p-adic integers, which are not finite expressions. Second, if g_{v} ∈ Q[x], then the entries of T_{A}(g_{v}) are integers bounded by \frac{1}{2}p^{b}, and these integers give some partial information about the coefficients of g_{v}. It would be inefficient to have this information in the lattice. Both problems are solved by cutting each entry of T_{A}(f_{i}) on two sides. If t is such an entry, then the p-adic integer t can be written as t = ∑_{i=0}^{∞} t_{i}p^{i} with t_{i} integers and −\frac{p}{2} < t_{i} ≤ \frac{p}{2}. Choose a > b, then cut such t by replacing it with ∑_{i=b}^{a−1} t_{i}p^{i−b}. So the powers ≥ a and the powers < b of p in t are removed. The first causes the expression to be finite, and the second removes unnecessary information about the coefficients of g from the lattice. Denote the result of this cutting by T_{A}^{b,a}(f_{i}). Let e_{1}, …, e_{n} be the standard basis vectors, so g_{e_{i}} = f_{i}. Denote V_{i} = (e_{i}, T_{A}^{b,a}(f_{i})) as the concatenation of the vectors e_{i} and T_{A}^{b,a}(f_{i}). The number of entries is n + s which is a little more than n. Denote E_{j}, j ∈ {1, …, s} as the vector with n + s entries, all 0 except for the n + j’th entry which is p^{a−b}.

The n + s vectors V_{i} and E_{j} are now the input vectors for LLL. To find the set B, calculate the short vectors in the lattice spanned by the V_{i} and E_{j}, then take the projection on the first n entries, and then reduce those vectors to echelon form. The resulting vectors form the set B, provided that a, b and the other parameters in the algorithm were set properly. This can be verified; the polynomials g_{v} for v in the calculated set B are automatically irreducible if they are in Q[x], so to verify the correctness of B one only needs to check that g_{v} ∈ Q[x] for all v ∈ B.

The reason that the LLL algorithm lets us find the vectors v for which g_{v} ∈ Q[x] is because for those v, the entries of T_{A}(g_{v}) are integers bounded by \frac{1}{2}p^{b}, hence T_{A}^{b,a}(g_{v}) = 0. Now ∑ v_{i}T_{A}^{b,a}(f_{i}) is almost the same as T_{A}^{b,a}(g_{v}) = 0, except for some round-off errors (caused by cutting the p-adic numbers) which must be of the form ϵ_{1} + ϵ_{2}p^{a−b}, where ϵ_{1}, ϵ_{2} are small. The vector ∑ v_{i}V_{i} = (v, ∑ v_{i}T_{A}^{b,a}(f_{i})) is in the lattice. After reducing with the vectors E_{i}, all entries are small; the first n entries are all 0 or 1, and the last s entries are small as well. So ∑ v_{i}V_{i} is a short vector. When this vector is found by LLL, v can be read off by taking the first n entries.

There is a lot of freedom in the choice of the numbers p^{a−b} and s so one can choose the size of the LLL input vectors. For efficiency, the size should be not too large, but the size should also not be too small because LLL can only find the short vectors if the remaining vectors are sufficiently long in comparison. The number s(a − b)log(p) should be O(n^{2}), and should be independent of N and D.

3 The i’th trace

Definition 1 The i’th trace Tr_{i}(g) of a polynomial g is defined as the sum of the i’th powers of the roots (counted with multiplicity) of g.

It is clear that

Tr_{i}(f_{1}) + Tr_{i}(f_{2}) = Tr_{i}(f_{1}f_{2})

for any two polynomials f_{1}, f_{2}. Suppose g = ∑ c_{i}x^{i} is monic of degree d. Then Tr_{i}(g) for i = 1, …, k can be determined from c_{d−i} for i = 1, …, k with the Newton relations, and vice versa.

Now choose some i_{1}, i_{2}, …, i_{s}, and for g ∈ Q_{p}[x] let T_{A}(g) be a vector whose entries are the p-adic numbers Tr_{i_{1}}(g), …, Tr_{i_{s}}(g) multiplied by some integer m. The integer m is chosen in such a way that if g is a factor of f in Q[x], then the entries of T_{A}(g) are integers. If f is monic and has integer coefficients then m = 1.

The number s is normally chosen much smaller than n or degree(g), so T_{A}(g) will only contain partial information about the coefficients of g. By computing a bound for the absolute value of the complex roots of f, it is easy to bound Tr_{i}(g) for any factor g ∈ Q[x] of f, so it is easy to calculate a number b such that the absolute values of the entries of T_{A}(g) are bounded by \frac{1}{2}p^{b}.

We use T_{A}(g) to fix the problem that g_{v} does not depend linearly on v. There is also another way to fix this problem: In [3] Victor Miller uses idempotents to factor in Q[x]. The main difference with our algorithm is that our algorithm is closer to Zassenhaus’ algorithm, because only the 0–1 vectors are computed with integer-relation-finding or LLL; the factors g themselves are constructed like in [1]. Millers algorithm is less similar to [1] but is closer to [2] in the sense that everything is computed with integer-relation-finding, more precisely: it calculates the 0–1 vector and the idempotent e simultaneously, and if e is a non-trivial idempotent then gcd(e, f) ∈ Q[x] is a non-trivial factor of f. In our algorithm, besides the 0–1 vector, no information about g is calculated with LLL, because the value of T_{A}(g) which contains information about g is precisely what is being cut away when all powers < b of p were removed.

References

[1] H. Zassenhaus, On Hensel Factorization, I., Journal of Number Theory 1, 291–311 (1969).

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

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

[4] M. van Hoeij, Factoring polynomials and the knapsack problem, preprint available from http://www.math.fsu.edu/~hoeij/ accepted for Journal of Number Theory (2000).