Vol. 2, 2019

 Recent Volumes 2: ANTS XIII 1: ANTS X
 The Open Book Series About the Series Ethics Statement Other MSP Publications
Counting roots for polynomials modulo prime powers

Qi Cheng, Shuhong Gao, J. Maurice Rojas and Daqing Wan

Vol. 2 (2019), No. 1, 191–205
Abstract

Suppose $p$ is a prime, $t$ is a positive integer, and $f\phantom{\rule{0.3em}{0ex}}\in \phantom{\rule{0.3em}{0ex}}ℤ\left[x\right]$ is a univariate polynomial of degree $d$ with coefficients of absolute value $<\phantom{\rule{0.3em}{0ex}}{p}^{t}$. We show that for any fixed $t$, we can compute the number of roots in $ℤ∕\left({p}^{t}\right)$ of $f$ in deterministic time ${\left(dlogp\right)}^{O\left(1\right)}$. This fixed parameter tractability appears to be new for $t\ge 3$. A consequence for arithmetic geometry is that we can efficiently compute Igusa zeta functions $Z$, for univariate polynomials, assuming the degree of $Z$ is fixed.

Keywords
polynomials, root counting, prime power
Mathematical Subject Classification 2010
Primary: 11Y16, 13P15