Vol. 2, 2019

 Download this article For screen For printing
 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
Milestones
Received: 1 March 2018
Revised: 14 June 2018
Accepted: 12 September 2018
Published: 13 February 2019
Authors
 Qi Cheng School of Computer Science University of Oklahoma Norman, OK United States Shuhong Gao Department of Mathematical Sciences Clemson University Clemson, SC United States J. Maurice Rojas Department of Computer Science and Engineering TAMU College Station, TX United States Daqing Wan Department of Mathematics University of California, Irvine Irvine, CA United States