#### Vol. 2, 2019

 Recent Volumes 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index MSP Books and Monographs 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