Factoring with LLL when the form of the factors is given

Given a degree $$2k$$ reducible polynomial

$$f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$$

with

$$\text{gcd}(a_{2k},\dots,a_0)=1$$ that is known to be of the form $$f_1(x)f_2(x)$$ with $$\text{deg}\big(f_i(x)\big)=\frac{\text{deg}(f(x))}{2}=k$$ and each $$f_i(x)$$ irreducible.

Can the LLL algorithm be used to factor $$f(x)$$ in polynomial time and what is the complexity?

Note that $$\text{gcd}(a_{2k},\dots,a_0)=1$$ makes $$f(x)$$ primitive.

This answer tells that such polynomials have efficient factorization algorithms. Although the precise method is not mentioned there I belive LLL suffices and hence the question here. If LLL does do the job, can its complexity be improved from $$(2k)^{6+\epsilon}$$ arithmetic operations which is needed if the form of the factors are unknown.

Refer here for complexity of factoring primitive polynomials with integer ocefficents where the phrase

We also mention Schönhage's method using $$O(n^6+n^4\log_2^2l)$$ bit operations for factoring polynomials with integer coefficients ($$l$$ is the length of the coefficients)

is used. $$n$$ is the degree and it corresponds to $$2k$$ here.

• You want the coefficients of $f_1(x)$ and $f_2(x)$ integer as well? Nov 20 '13 at 17:56
• @JAS: Could you give us an idea of why you think LLL could be used to solve the problem. Nov 21 '13 at 5:56
• $f(x)\in\Bbb Z[x]$ is primitive. Nov 21 '13 at 8:11

Yes, assuming you want both $$f_1(x)$$ and $$f_2(x)$$ with integer coefficients.

One of the reasons why LLL is so popular is precisely because it gives a polynomial time algorithm to factor polynomials with integer coefficients.

For an excellent introduction, I recommend C. Yap's "Fundamental Problems in Algorithmic Algebra" (available online, for free), specifically chapter 9 "Lattice Reduction and Applications" (section 9.6).

Following Yap, choose an approximation, $$\alpha$$, of a (complex) root for $$f(x)$$. Setup the lattice reduction with the following basis:

$$B_k = \begin{bmatrix} \text{Re}(\alpha^0) & \text{Re}(\alpha^1) & \text{Re}(\alpha^2) & \cdots & \text{Re}(\alpha^k) \\ \text{Im}(\alpha^0) & \text{Im}(\alpha^1) & \text{Im}(\alpha^2) & \cdots & \text{Im}(\alpha^k) \\ c & 0 & 0 & \cdots & 0 \\ 0 & c & 0 & \cdots & 0 \\ 0 & 0 & c & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & c \end{bmatrix}$$

Choosing $$c = 2^{-4t^3}$$, with $$\alpha$$ to have $$O(t^3)$$ bits for each of the real and complex portions. Here, $$t = \log ||f(x)||_{\infty}$$ (that is, the cube of the number of bits of the maximum coefficient of $$f(x)$$).

Quoted from FPiAA:

Theorem 9 Given a basis $$A \in \mathbb{Q}^{n \times m}$$, we can compute a reduced basis $$B$$ with $$\Lambda(A) = \Lambda(B)$$ using $$O(n^5(s + \log n))$$ arithmetic operations, where s is the maximum bit size of entries in $$A$$

This gives us the (polynomial) run time. Proof of correctness that for a properly setup lattice will give you the minimal factor of a reducible polynomial is a bit more involved, but please refer to theorem 14 of the same chapter to see the relation between the reduced basis and the minimal polynomial.

By setting up the basis with dimension $$n=k$$ you can easily see the bound as roughly $$O(k^5( \lg^3(||f(x)||_{\infty}) + \log n))$$.

Since, by assumption, you know the degree of $$f_1(x)$$ and $$f_2(x)$$, the lattice reduction algorithm only needs to be run once to find one of the two factors of $$f(x)$$. You can then use the discovered $$f_j(x)$$ to find the other by standard polynomial division.

The original paper by Lenstra, Lenstra and Lovasz, "Factoring polynomials with rational coefficients", is also quite readable and I found it to be a good compliment to Yap's introduction.

• So the complexity if the form of factors is given as in the question is $O(k^{5+\epsilon})$ (or $O(k^{8+\epsilon})$) rather than $O((2k)^{6+\epsilon})$ (or $O((2k)^{9+\epsilon})$) arithmetic (or bit) operations assuming fast integer multiplication? Nov 22 '13 at 7:47
• Just to point out, there is a typo in the $B_k$ matrix in this answer. The second row should be $\textrm{Im}(\alpha^0) \cdots \textrm{Im}(\alpha^k)$ as is written in equation 21 of lecture IX, page 248 of Yap's book. Sep 10 '15 at 2:16
• @qwerty1793, thanks for pointing it out. It's been fixed. Sep 10 '15 at 5:12
• The link to the book chapter is broken, but the Internet Archive still has it: web.archive.org/web/20151015200136/http://cs.nyu.edu/~yap/book/… . The rest of the book was also archived: web.archive.org/web/20151020090714/http://cs.nyu.edu/~yap/book/… Dec 27 '19 at 9:35
• In the running time bound, shouldn't the cube be outside the log, not inside? That is, $O(k^5( \lg(||f(x)||_{\infty})^3 + \log n))$ instead of $O(k^5( \lg(||f(x)||_{\infty}^3) + \log n))$. Dec 27 '19 at 9:38