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


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

author list (cited authors)

  • Kopp, L., Randall, N., Rojas, J. M., & Zhu, Y.

complete list of authors

  • Kopp, Leann||Randall, Natalie||Rojas, J Maurice||Zhu, Yuyu

Book Title

  • arXiv

publication date

  • August 2018