Counting Roots of Polynomials Over Prime Power Rings

11/03/2017

∙

by   Qi Cheng, et al.

∙

0

∙

share

Suppose p is a prime, t is a positive integer, and f∈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 Z/(p^t) of f in deterministic time (d+ p)^O(1). This fixed parameter tractability appears to be new for t≥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.