Randomized Polynomial-Time Root Counting in Prime Power Rings

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
ight)$ within time $d^3(klog 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.

Randomized Polynomial-Time Root Counting in Prime Power Rings Institutional Repository Document