Randomized Polynomial-Time Root Counting in Prime Power Rings

Suppose $k,p\text{\hspace{0.17em}⁣}\in \text{\hspace{0.17em}⁣}\mathbb{N}$ with $p$ prime and $f\text{\hspace{0.17em}⁣}\in \text{\hspace{0.17em}⁣}\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}\mathrm{/}\text{\hspace{0.17em}⁣}\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.