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 mod p 2 is irreducible, but x 2 + p x 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 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 ) mod p k ( x ) for some irreducible mod p . We could efficiently solve the latter for k 4 , by incrementally transforming E ( y ) . Moreover, we discover an efficient and strong generalization of Hensel lifting to lift factors of f ( x ) mod p to those mod p 4 (if possible). This was previously unknown, as the case of repeated factors of f ( x ) mod p forbids classical Hensel lifting.