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 ... more >>>