How to split a quartic into two quadratics?

I have a quartic in $\Bbb Z[x]$ with very large coefficients that I know splits into two quadratics in $\Bbb Z[x]$. What is the best way to do find the quadratics?

A general method always available is to first factor the polynomial $F(x)$ modulo some prime $p$ (possible a small one), and then Hensel lift that to a factorization modulo progressively higher powers of that prime. Given that you know there exists a factorization over $\Bbb{Z}$, the sequence of those modulo $p^n$ factorizations will stabilize when $n$ is large enough, and you get a fairly good idea of the actual factors (it is simple to verify a candidate factorization).

1. For the Hensel lifting to work out, the two factors modulo $p$ should be distinct. Unless the two quadratic factors your polynomial has are equal they will also be distinct modulo most primes. You can detect this by checking whether $\gcd_{\Bbb{Z}[x]}(F(x),F'(x))=1$ or not. A repeated factor of $F(x)$ will show as a common factor of $F(x)$ and $F'(x)$.
2. For simplicity it may be better not to use a prime $p$ such that your polynomial also has linear factors modulo that prime. You can probably use linear factors as well, but if your pair them up incorrectly, then the Hensel lifting may not converge. If you know that the quadratic factors of $F(x)$ are irreducible over $\Bbb{Z}$, then they will remain so modulo some primes (Note: this does not hold for polynomials of degree $>2$). I admit to not being certain what is best here, if you get four distinct linear factors modulo your chosen $p$. May be it is best to try out lifting all the three quadratic $\times$ quadratic factorizations that you get out of that?
3. To find the factorization modulo $p$ I would start with Cantor-Zassenhaus algorithm, because it is simple. Any irreducible linear or quadratic polynomial with coefficients in $\Bbb{Z}_p$ is a factor of $x^{p^2}-x=x(x^{p^2-1}-1).$ Furthermore, a factor with the property that its zeros (in the field $\Bbb{F}_{p^2}$) are non-zero squares will also be a factor of $Q(x):=x^{(p^2-1)/2}-1$. With a little bit of luck the zeros of one factor of $F(x)$ are squares and those of the other are not. The zeros of an irreducible quadratic either both are squares or both are non-squares, so this is a 50-50 chance. If that happens, then the factor with zeros in $(\Bbb{F}_{p^2}^*)^2$ is the common factor $\gcd_{\Bbb{F}_p[x]}(F(x),Q(x))$, and can be calculated efficiently with Euclid's algorithm. The other factor can then be found by long division.
4. To improve the odds of success you can do the following modifications (this is the non-deterministic part in C-Z). Instead of calculating just $\gcd(F(x),Q(x))$ you can also calculate $\gcd(F(x-a),Q(x))$ for several $a\in\Bbb{Z}_p$. If $P(x)$ is an irreducible quadratic factor of $F(x)$ modulo $p$, then for a random choice of $a$ there is next to no correlation between "the zeros of $P(x)$ are squares" and "the zeros of $P(x-a)$ are squares". Therefore, statistically speaking, each try with a different $a$ halves your probability of failure. Of course, $P(x-a)$ is a factor of $F(x-a)$, iff $P(x)$ is a factor of $F(x)$.

Example.

Find the factors of $F(x)=x^4+2x^3-123x^2+524x-341$

(I know that this too small to be of interest to you, and here trial-and-error would quickly do it. This is just for demonstration).

First we check that $\gcd_{\Bbb{Q}[x]}(F(x),F'(x))=1$, so there are no repeated factors. I skip the runs of (generalized) Euclid's algorithm.

Let's try to factor $F(x)$ modulo $p=5$. First try with $a=0$. $$ \gcd\nolimits_{\Bbb{F}_5[x]}(F(x),x^{12}-1)=x^4+2x^3+2x^2+4x+4\equiv F(x)\pmod 5. $$ This was no good. Looks like all the zeros of $F(x)$ are squares in $\Bbb{F}_{25}$. Let's try instead $$ F(x+1)\equiv x^4+x^3-x^2+3x+3\pmod5. $$ We get $$ \gcd\nolimits_{\Bbb{F}_5[x]}(F(x+1),x^{12}-1)=x^2+x+1. $$ That's more like it! We know that one of the modulo $5$ factors of $F(x)$ is $$G_1(x)=(x-1)^2+(x-1)+1\equiv x^2+4x+1\pmod5.$$ The other factor is gotten by long division, $H_1(x)=F(x)/G_1(X)=x^2+3x+4$, so we got $$ F(x)\equiv G_1(x)H_1(x)\pmod 5. $$

An aside: Why $p=5$? Modulo $p=2$ $F(x)\equiv(x^2+x+1)^2$ is a square, and modulo $p=3$ we have $F(x)\equiv(x+2)^4$. Neither of those primes can be used, because Hensel lifting requires coprime factors. The smaller the prime, the higher the chance of repeated factors.

On with the Hensel lifting. Next we want to find a factorization of $F(x)$ modulo $5^2=25$. Because $\gcd_{\Bbb{F}_5}(G_1(x),H_1(x))=1$ Hensel's lemma guarantees the existence of monic polynomials $G_2(x), H_2(x)$ such that $G_2(x)H_2(x)\equiv F(x)\pmod{25}$, and $G_1\equiv G_2, H_1\equiv H_2\pmod5$. These are found as follows. Interpreting the polynomials $G_1,H_1$ to have integer coefficients we are looking for linear polynomials $K_2,L_2$ with integer coefficients such that $$ F\equiv(G_1+5K_2)(H_1+5L_2)\equiv G_1H_1+5(K_2H_1+L_2G_1)\pmod{25}. $$ Because $$ F-G_1H_1=-5x^3-140x^2+505x-345=5(-x^3-28x^2+101x-69)\equiv 5(4x^3+2x^2+x+1)\pmod{25} $$ we want to find $K_2,L_2\in\Bbb{F}_5[x]$ such that $$ K_2H_1+L_2G_1=4x^3+2x^2+x+1:=U(x)\in\Bbb{F}_5[x]. $$ Here $U(x)\equiv 3x\pmod{G_1(x)}$ and $U(x)\equiv 1\pmod{H_1(x)}$, so we want $L_2G_1\equiv 1\pmod{H_1}$ and $K_2H_1\equiv 3x\pmod{G_1}$.

A run of the Extended Euclid's algorithm in the ring $\Bbb{F}_5[x]$ gives us the identity $$ 1=\gcd(G_1,H_1)=(2x+2)G_1+(3x+1)H_1, $$ and we can read the inverse of $G_1$ modulo $H_1$ (resp. inverse of $H_1$ modulo $G_1$) from this. Therefore $$ K_2\equiv 3xH_1^{-1}=3x(1+3x)\equiv2x+1\pmod{G_1}. $$ and $$ L_2\equiv 1\cdot G_1^{-1}=(2x+2)\equiv 2x+2\pmod{H_1}, $$ This gives us the lifts $$ G_2(x)=G_1(x)+5K_2(x)=x^2+14x+6 $$ and $$ H_2(x)=H_1(x)+5L_2(x)=x^2+13x+14. $$ As a check we calculate $$ F-G_2H_2=-25x^3-325x^2+250x-425, $$ and see that it is, indeed, a multiple of $25$.

Here we can either continue the lifting to find a factorization modulo $5^3=125$, or do a bit of experimenting. I skip the lifting, and simply observe that $$ (G_2-25x+25)(H_2-25)=F, $$ so the factorization is $$ F(x)=(x^2-11x+31)(x^2+13-11). $$ A big tip off (to anyone doing pencil and paper work) in the last step is the constant term $-341=-11\cdot31$ of $F(x)$.