<p>Yes, assuming you want both <span class="math-container">$f_1(x)$</span> and <span class="math-container">$f_2(x)$</span> with integer coefficients.</p>

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

<p>For an excellent introduction, I recommend C. Yap's <a href="http://cs.nyu.edu/yap/book/berlin/" rel="nofollow noreferrer">"Fundamental Problems in Algorithmic Algebra"</a> (available online, for free), specifically chapter 9 <a href="http://cs.nyu.edu/~yap/book/alge/ftpSite/l9.ps.gz" rel="nofollow noreferrer">"Lattice Reduction and Applications"</a> (section 9.6).  </p>

<p>Following Yap, choose an approximation, <span class="math-container">$\alpha$</span>, of a (complex) root for <span class="math-container">$f(x)$</span>.  Setup the lattice reduction with the following basis:</p>

<p><span class="math-container">$$ B_k = \begin{bmatrix} 
\text{Re}(\alpha^0) &amp; \text{Re}(\alpha^1) &amp; \text{Re}(\alpha^2) &amp; \cdots &amp; \text{Re}(\alpha^k) \\
\text{Im}(\alpha^0) &amp; \text{Im}(\alpha^1) &amp; \text{Im}(\alpha^2) &amp; \cdots &amp; \text{Im}(\alpha^k) \\
c &amp; 0 &amp; 0 &amp; \cdots &amp; 0 \\
0 &amp; c &amp; 0 &amp; \cdots &amp; 0 \\
0 &amp; 0 &amp; c &amp; \cdots &amp; 0 \\
\vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
0 &amp; 0 &amp; 0 &amp; \cdots &amp; c 
 \end{bmatrix}
$$</span></p>

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

<p>Quoted from FPiAA:</p>

<blockquote>
  <p><strong>Theorem 9</strong> <em>Given a basis <span class="math-container">$A \in \mathbb{Q}^{n \times m}$</span>, we can compute a reduced basis <span class="math-container">$B$</span> with <span class="math-container">$\Lambda(A) = \Lambda(B)$</span> using <span class="math-container">$O(n^5(s + \log n))$</span> arithmetic operations, where s is the maximum bit size of entries in <span class="math-container">$A$</span></em></p>
</blockquote>

<p>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.</p>

<p>By setting up the basis with dimension <span class="math-container">$n=k$</span> you can easily see the bound as roughly <span class="math-container">$O(k^5( \lg^3(||f(x)||_{\infty}) + \log n))$</span>.</p>

<p>Since, by assumption, you know the degree of <span class="math-container">$f_1(x)$</span> and <span class="math-container">$f_2(x)$</span>, the lattice reduction algorithm only needs to be run once to find one of the two factors of <span class="math-container">$f(x)$</span>.  You can then use the discovered <span class="math-container">$f_j(x)$</span> to find the other by standard polynomial division.</p>

<p>The original paper by Lenstra, Lenstra and Lovasz, <a href="http://www.math.elte.hu/~lovasz/scans/lll.pdf" rel="nofollow noreferrer">"Factoring polynomials with rational coefficients"</a>, is also quite readable and I found it to be a good compliment to Yap's introduction.</p>

CC BY-SA 3.0
2013-11-22T07:47:22.740Z
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?
Turbo
CC BY-SA 3.0
2015-09-10T02:16:58.093Z
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.
qwerty1793
CC BY-SA 3.0
2015-09-10T05:12:57.463Z
@qwerty1793, thanks for pointing it out.  It's been fixed.
user834
CC BY-SA 4.0
2019-12-27T09:35:01.080Z
The link to the book chapter is broken, but the Internet Archive still has it: https://web.archive.org/web/20151015200136/http://cs.nyu.edu/~yap/book/alge/ftpSite/l9.ps.gz . The rest of the book was also archived: https://web.archive.org/web/20151020090714/http://cs.nyu.edu/~yap/book/alge/ftpSite/
qbt937
CC BY-SA 4.0
2019-12-27T09:38:05.873Z
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))$.
qbt937
CC BY-SA 4.0
2020-05-23T13:21:43.487Z
@qbt937, quite right, fixed
user834
CC BY-SA 4.0
2022-01-26T20:02:27.177Z
I wrote an implementation of this algorithm here: https://github.com/geodavic/poly_factor

There is also a public API and a website to test it out. See the README.
gdavtor
CC BY-SA 4.0
2013-11-21T19:56:37.847Z
2020-05-23T13:21:27.473Z
2020-05-23T13:21:27.473Z
user834
<p>Given a degree <span class="math-container">$2k$</span> reducible polynomial </p>

<p><span class="math-container">$$f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$$</span> </p>

<p>with </p>

<p><span class="math-container">$$\text{gcd}(a_{2k},\dots,a_0)=1$$</span> that is known to be of the form <span class="math-container">$f_1(x)f_2(x)$</span> with <span class="math-container">$\text{deg}\big(f_i(x)\big)=\frac{\text{deg}(f(x))}{2}=k$</span> and each <span class="math-container">$f_i(x)$</span> irreducible.</p>

<p>Can the <a href="https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" rel="nofollow noreferrer">LLL algorithm</a> be used to factor <span class="math-container">$f(x)$</span> in polynomial time and what is the complexity?</p>

<p>Note that <span class="math-container">$\text{gcd}(a_{2k},\dots,a_0)=1$</span> makes <span class="math-container">$f(x)$</span> primitive.</p>

<p><a href="https://math.stackexchange.com/questions/285649/irreducible-polynomials-in-mathbbzx">This answer</a> 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 <span class="math-container">$(2k)^{6+\epsilon}$</span> arithmetic operations which is needed if the form of the factors are unknown.</p>

<p><a href="http://www.tankonyvtar.hu/en/tartalom/tamop425/0046_algorithms_of_informatics_volume1/ch05s05.html" rel="nofollow noreferrer">Refer here</a> for complexity of factoring primitive polynomials with integer ocefficents where the phrase </p>

<blockquote>
  <p>We also mention Schönhage's method using <span class="math-container">$O(n^6+n^4\log_2^2l)$</span>  bit operations for factoring polynomials with integer coefficients (<span class="math-container">$l$</span> is the length of the coefficients)</p>
</blockquote>

<p>is used. <span class="math-container">$n$</span> is the degree and it corresponds to <span class="math-container">$2k$</span> here.</p>

CC BY-SA 3.0
2013-11-20T17:56:09.103Z
You want the coefficients of $f_1(x)$ and $f_2(x)$ integer as well?
user834
CC BY-SA 3.0
2013-11-21T05:56:35.963Z
@JAS: Could you give us an idea of why you think LLL could be used to solve the problem.
Vivek Bagaria
CC BY-SA 3.0
2013-11-21T08:11:36.143Z
$f(x)\in\Bbb Z[x]$ is primitive.
Turbo
<ds.algorithms><polynomials><algebraic-complexity><factoring><lattice>
Factoring with LLL when the form of the factors is given
Turbo
# Factoring with LLL when the form of the factors is given

(Asked by: username_0 on 2013-11-20)

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](https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_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](https://math.stackexchange.com/questions/285649/irreducible-polynomials-in-mathbbzx) 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](http://www.tankonyvtar.hu/en/tartalom/tamop425/0046_algorithms_of_informatics_volume1/ch05s05.html) 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.

**Tags:** ds.algorithms, polynomials, algebraic-complexity, factoring, lattice

> **Comments:**
> **username_1**: You want the coefficients of $f_1(x)$ and $f_2(x)$ integer as well?  
> **username_2**: @JAS: Could you give us an idea of why you think LLL could be used to solve the problem.  
> **username_0**: $f(x)\in\Bbb Z[x]$ is primitive.  

---

## 1 answers

### Answer by username_1 on 2013-11-21. Score: 9 | Accepted answer

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"](http://cs.nyu.edu/yap/book/berlin/) (available online, for free), specifically chapter 9 ["Lattice Reduction and Applications"](http://cs.nyu.edu/~yap/book/alge/ftpSite/l9.ps.gz) (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"](http://www.math.elte.hu/~lovasz/scans/lll.pdf), is also quite readable and I found it to be a good compliment to Yap's introduction.

> **Comments:**
> **username_0**: 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?  
> **username_3**: 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.  
> **username_1**: @username_3, thanks for pointing it out.  It's been fixed.  
> **username_4**: The link to the book chapter is broken, but the Internet Archive still has it: https://web.archive.org/web/20151015200136/http://cs.nyu.edu/~yap/book/alge/ftpSite/l9.ps.gz . The rest of the book was also archived: https://web.archive.org/web/20151020090714/http://cs.nyu.edu/~yap/book/alge/ftpSite/  
> **username_4**: 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))$.  
> **username_1**: @username_4, quite right, fixed  
> **username_5**: I wrote an implementation of this algorithm here: https://github.com/geodavic/poly_factor  There is also a public API and a website to test it out. See the README.  

---

