Vol. 2, 2019

Download this article
Download this article For screen
For printing
Recent Volumes
2: ANTS XIII
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
 
Other MSP Publications
Counting roots for polynomials modulo prime powers

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

Vol. 2 (2019), No. 1, 191–205
Abstract

Suppose p is a prime, t is a positive integer, and f [x] is a univariate polynomial of degree d with coefficients of absolute value < pt . We show that for any fixed t, we can compute the number of roots in (pt) of f in deterministic time (dlogp)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.

Keywords
polynomials, root counting, prime power
Mathematical Subject Classification 2010
Primary: 11Y16, 13P15
Milestones
Received: 1 March 2018
Revised: 14 June 2018
Accepted: 12 September 2018
Published: 13 February 2019
Authors
Qi Cheng
School of Computer Science
University of Oklahoma
Norman, OK
United States
Shuhong Gao
Department of Mathematical Sciences
Clemson University
Clemson, SC
United States
J. Maurice Rojas
Department of Computer Science and Engineering
TAMU
College Station, TX
United States
Daqing Wan
Department of Mathematics
University of California, Irvine
Irvine, CA
United States