  Suppose $k,p\!\in\!\mathbb{N}$ with $p$ prime and $f\!\in\!\mathbb{Z}[x]$ is
a univariate polynomial with degree $d$ and all coefficients having absolute
value less than $p^k$. We give a Las Vegas randomized algorithm that computes
the number of roots of $f$ in $\mathbb{Z}/\!\left(p^k\right)$ within time
$d^3(k\log p)^{2+o(1)}$. (We in fact prove a more intricate complexity bound
that is slightly better.) The best previous general algorithm had
(deterministic) complexity exponential in $k$. We also present some
experimental data evincing the potential practicality of our algorithm.
