Randomized Polynomial-Time Root Counting in Prime Power Rings

Abstract

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.

11 pages, 3 figures. Qi Cheng just pointed out that [3, Cor. 4, Pg. 16] proves a generalization of the main result (Theorem 1.1), and gives a sharper complexity bound. Nevertheless, the underlying algorithms are approached differently, so the development of our paper (the recursion tree structure, in particular) may still be of value