Thirteenth Algorithmic Number Theory Symposium ANTS-XIII University of Wisconsin, Madison July 16 – 20, 2018 Thirteenth Algorithmic Number Theory Symposium (ANTS-XIII) July 16 – 20, 2018

Counting roots for polynomials modulo prime powers

Qi Cheng, Shuhong Gao, J. Maurice Rojas and Daqing Wan

Abstract: Suppose p is a prime, t is a positive integer, and f in 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 log 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.

Published Paper
Talk Slides