Factoring with LLL when the form of the factors is given
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.