Given a degree $2k$ reducible polynomial

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


$$\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.

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

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – Turbo
    Nov 22, 2013 at 7:47
  • $\begingroup$ 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. $\endgroup$
    – qwerty1793
    Sep 10, 2015 at 2:16
  • $\begingroup$ @qwerty1793, thanks for pointing it out. It's been fixed. $\endgroup$
    – user834
    Sep 10, 2015 at 5:12
  • 1
    $\begingroup$ 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/… $\endgroup$
    – qbt937
    Dec 27, 2019 at 9:35
  • 1
    $\begingroup$ 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))$. $\endgroup$
    – qbt937
    Dec 27, 2019 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.