  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
\bmod p^2$ is irreducible, but $x^2+px \bmod 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 \leq 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) \bmod p^k$ to that
of {\em root finding} in a related polynomial $E(y) \bmod\langle p^k,
\varphi(x)^\ell \rangle$ for some irreducible $\varphi \bmod p$. We could
efficiently solve the latter for $k\le4$, by incrementally transforming $E(y)$.
Moreover, we discover an efficient and strong generalization 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.
