Suppose
$p$ is a prime,
$t$ is a positive integer, and
$f\phantom{\rule{0.3em}{0ex}}\in \phantom{\rule{0.3em}{0ex}}\mathbb{Z}\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 $\mathbb{Z}\u2215\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.
