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.

arXiv comment11 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

References in corpus (3)

• Counting points on varieties over finite fields of small characteristic
• Counting Roots of Polynomials Over Prime Power Rings
• Computing Igusa's local zeta functions of univariate polynomials, and linear feedback shift registers