Abstract

Suppose $p$ is a prime, $t$ is a positive integer, and $f\in \mathbb{Z}\left[x\right]$ 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}∕\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

Mathematical Subject Classification 2010

Milestones

Authors