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.
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) &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}
$$

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.