Efficiently factoring polynomials modulo p⁴

Abstract

Polynomial factoring has famous practical algorithms over fields-- finite, rational and p-adic. However, modulo prime powers, factoring gets harder because there is non-unique factorization and a combinatorial blowup ensues. For example, x^2+p \bmod p^2 is irreducible, but x^2+px \bmod p^2 has exponentially many factors! We present the first randomized poly(\deg f, łog p) time algorithm to factor a given univariate integral f(x) modulo p^k, for a prime p and k łeq 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) mod p^k to that of \em root finding in a related polynomial E(y) \bmodłangle p^k, \varphi(x)^\ell \rangle for some irreducible \varphi \bmod p. We can efficiently solve the latter for kłe4, by incrementally transforming E(y). Moreover, we discover an efficient refinement of Hensel lifting to lift factors of f(x) \bmod p to those \bmod\ p^4 (if possible). This was previously unknown, as the case of repeated factors of f(x) \bmod p forbids classical Hensel lifting.