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

Finding an irreducible factor, of a polynomial f(x) modulo a prime p, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of f\bmod p. We can ask the same question modulo prime-powers p^k. The irreducible ... more >>>