期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-15
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Igusa’s local zeta function Zf,p(s) is the generating function that counts the number of integral roots, Nk(f), of f(x) mod p k , for all k. It is a famous result, in analytic number theory, that Zf,p is a rational function in Q(p s ). We give an elementary proof of this fact for a univariate polynomial f. Our proof is constructive as it gives a closed-form expression for the number of roots Nk(f). Our proof, when combined with the recent root-counting algorithm of (Dwivedi, Mittal, Saxena, CCC, 2019), yields the first deterministic poly(|f|, log p) time algorithm to compute Zf,p(s). Previously, an algorithm was known only in the case when f completely splits over Qp; it required the rational roots to use the concept of generating function of a tree (Z´u˜niga-Galindo, J.Int.Seq., 2003).
