Denote the polynomial to be factored by $f(x) \in \mathbb{Z}[x]$. Here is a rough overview of what is done in the Berlekamp-Zassenhaus algorithm:
- Assume $f(x)$ is primitive and square-free.
- Choose suitable prime $p$.
- One then factors $h(x)$ in a way such that $f(x) = \prod_{i = 1}^{r}{u_i(x)}$ over $\mathbb Z_p$, and $\operatorname{lc} u_1(x) = \operatorname{lc} f(x) \bmod{p}$ while $\operatorname{lc} u_2(x) = \dots = \operatorname{lc} u_r(x) = 1$.
- Then the factors are (quadratically) Hensel lifted to modulo $p^K$ for suitably large $K$, so that $f(x) \equiv \prod u_i^{(K)} \bmod p^K$ and preserving the $\operatorname{lc}$ properties in modulo $p^K$. (Here $u_i^{(K)}(x)$, $i = 1, \dots, r$, are the lifted factors).
Finally, one attempts to retrive the factors in $\mathbb Z[x]$ from these $u_i^{(K)}(x)$. This is done (essentially) by testing whether various combinations of $u_i^{(K)}(x)$ divide $f(x)$. Here is an example pseudocode from Computing, Suppl. 4, 95–113 (1982) by E. Kalfoten:
Question
Notice that at first, $h(x) := f(x)$. This is updated if a factor $g(x)$ is found to $h(x) / g(x)$.
In the forall loop, instead of simply taking combinations of $u_i^{(K)}(x)$ and testing for divisibility, one further multiplies the combination of $u_i^{(K)}(x)$ by $\operatorname{lc} h(x)$, reduces modulo $p^K$, and takes the primitive part. I can see that taking the primitive part can only be advantageous (and is compulsory because $f(x)$ is primitive, for instance). However, why multiplying by $\operatorname{lc} h(x)$ guarantees success is unclear to me.
I have seen specific examples where without this multiplication the factors of $f(x)$ are not retrieved, and with the multiplication, they are retrived.
- However, what is the rigorous yet assumingly simple explanation why the multiplication by $\operatorname{lc} h(x)$ and reducing modulo $p^K$ works? Why does it fix things?