Counting Roots for Polynomials Modulo Prime Powers

报告题目:Counting Roots for Polynomials Modulo Prime Powers




摘要: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 {\em 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 \geq 3$. A consequence for arithmetic geometry is that we can efficiently compute the Igusa zeta functions $Z$, for univariate polynomials, assuming the degree of $Z$ is fixed.

程岐教授简历:Dr. Qi Cheng is a Williams Company Foundation Presidential Professor in the School of Computer Science at the University of Oklahoma, where he joined in 2001. He received his PhD in Computer Science from University of Southern California in 2001. His research interests are in the areas of theoretical computer science, DNA/molecular computing, cryptography and computational number theory. He has published over 30 research articles in journals and conference proceedings.