Efficiently factoring polynomials modulo $p^4$

Abstract

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& $p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, $x^2+p\mathrm{mod}{p}^2$ is irreducible, but $x^2+px\mathrm{mod}{p}^2$ has exponentially many factors! We present the first randomized poly(deg $f,\log p$) time algorithm to factor a given univariate integral $f(x)$ modulo $p^k$, for a prime $p$ and $k\le 4$. Thus, we solve the open question of factoring modulo $p^3$ posed in (Sircana, ISSAC'17). Our method reduces the general problem of factoring $f(x)\mathrm{mod}{p}^k$ to that of {\em root finding} in a related polynomial $E(y)\mathrm{mod}⟨p^k,\phi (x{)}^{\ell }⟩$ for some irreducible $\phi \mathrm{mod}p$. We could efficiently solve the latter for $k\le 4$, by incrementally transforming $E(y)$. Moreover, we discover an efficient and strong generalization of Hensel lifting to lift factors of $f(x)\mathrm{mod}p$ to those $\mathrm{mod}{p}^4$ (if possible). This was previously unknown, as the case of repeated factors of $f(x)\mathrm{mod}p$ forbids classical Hensel lifting.

22 pages