Counting roots for polynomials modulo prime powers
Open Access Publications from the University of California

## Counting roots for polynomials modulo prime powers

• Author(s): Cheng, Qi
• Gao, Shuhong
• Rojas, J Maurice
• Wan, Daqing
• et al.

## Published Web Location

https://doi.org/10.2140/obs.2019.2.191
Abstract

Suppose $p$ is a prime, $t$ is a positive integer, and $f\!\in\!\mathbb{Z}[x]$ is a univariate polynomial of degree $d$ with coefficients of absolute value $<\!p^t$. We show that for any fixed $t$, we can compute the number of roots in $\mathbb{Z}/(p^t)$ of $f$ in deterministic time $(d+\log p)^{O(1)}$. This fixed parameter tractability appears to be new for $t\!\geq\!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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.