Randomized polynomial-time root counting in prime power rings

Kopp, Leann; Randall, Natalie; Rojas, J.; Zhu, Yuyu

doi:10.1090/mcom/3431

Randomized polynomial-time root counting in prime power rings
HTML articles powered by AMS MathViewer

by Leann Kopp, Natalie Randall, J. Maurice Rojas and Yuyu Zhu HTML | PDF

Math. Comp. 89 (2020), 373-385

Abstract:

Suppose $k,p\!\in \!\mathbb {N}$ with $p$ prime and $f\!\in \!\mathbb {Z}[x]$ is a univariate polynomial with degree $d$ and all coefficients having absolute value less than $p^k$. We give a Las Vegas randomized algorithm that computes the number of roots of $f$ in $\mathbb {Z}/\!\left (p^k\right )$ within time $d^3(k\log p)^{2+o(1)}$. (We in fact prove a more intricate complexity bound that is slightly better.) The best previous general algorithm had (deterministic) complexity exponential in $k$. We also present some experimental data evincing the potential practicality of our algorithm.

References

Martín Avendaño, Ashraf Ibrahim, J. Maurice Rojas, and Korben Rusek, Faster $p$-adic feasibility for certain multivariate sparse polynomials, J. Symbolic Comput. 47 (2012), no. 4, 454–479. MR 2890882, DOI 10.1016/j.jsc.2011.09.007
Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794
Jérémy Berthomieu, Grégoire Lecerf, and Guillaume Quintin, Polynomial root finding over local rings and application to error correcting codes, Appl. Algebra Engrg. Comm. Comput. 24 (2013), no. 6, 413–443. MR 3128698, DOI 10.1007/s00200-013-0200-5
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
David G. Cantor and Daniel M. Gordon, Factoring polynomials over $p$-adic fields, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 185–208. MR 1850606, DOI 10.1007/10722028_{1}0
W. Castryck, J. Denef, and F. Vercauteren, Computing zeta functions of nondegenerate curves, IMRP Int. Math. Res. Pap. (2006), Art. ID 72017, 57. MR 2268492
Antoine Chambert-Loir, Compter (rapidement) le nombre de solutions d’équations dans les corps finis, Astérisque 317 (2008), Exp. No. 968, vii, 39–90 (French, with French summary). Séminaire Bourbaki. Vol. 2006/2007. MR 2487730
Qi Cheng, Primality proving via one round in ECPP and one iteration in AKS, J. Cryptology 20 (2007), no. 3, 375–387. MR 2371220, DOI 10.1007/s00145-006-0406-9
Q. Cheng, S. Gao, J. M. Rojas, and D. Wan, Counting Roots for Polynomials Modulo Prime Powers, Proceedings of ANTS XIII (Algorithmic Number Theory Symposium, July 16–20, 2018, University of Wisconsin, Madison), Mathematical Sciences Publishers (Berkeley, California), to appear.
Alexandre L. Chistov, Efficient factoring polynomials over local fields and its applications, Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990) Math. Soc. Japan, Tokyo, 1991, pp. 1509–1519. MR 1159333
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Jan Denef, Report on Igusa’s local zeta function, Astérisque 201-203 (1991), Exp. No. 741, 359–386 (1992). Séminaire Bourbaki, Vol. 1990/91. MR 1157848
Shuhong Gao, Frank Volny IV, and Mingsheng Wang, A new framework for computing Gröbner bases, Math. Comp. 85 (2016), no. 297, 449–465. MR 3404457, DOI 10.1090/mcom/2969
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 3rd ed., Cambridge University Press, Cambridge, 2013. MR 3087522, DOI 10.1017/CBO9781139856065
Joachim von zur Gathen and Silke Hartlieb, Factoring modular polynomials, J. Symbolic Comput. 26 (1998), no. 5, 583–606. MR 1656549, DOI 10.1006/jsco.1998.0228
Jordi Guàrdia, Enric Nart, and Sebastian Pauli, Single-factor lifting and factorization of polynomials over local fields, J. Symbolic Comput. 47 (2012), no. 11, 1318–1346. MR 2927133, DOI 10.1016/j.jsc.2012.03.001
Jun-ichi Igusa, Complex powers and asymptotic expansions. I. Functions of certain types, J. Reine Angew. Math. 268(269) (1974), 110–130. MR 347753, DOI 10.1515/crll.1974.268-269.110
Kiran S. Kedlaya and Christopher Umans, Fast polynomial factorization and modular composition, SIAM J. Comput. 40 (2011), no. 6, 1767–1802. MR 2863194, DOI 10.1137/08073408X
A. R. Klivans, Factoring polynomials modulo composites, Master’s Thesis, Carnegie Mellon University Computer Science Technical Report CMU-CS-97-136, 1997.
Alan G. B. Lauder, Counting solutions to equations in many variables over finite fields, Found. Comput. Math. 4 (2004), no. 3, 221–267. MR 2078663, DOI 10.1007/s10208-003-0093-y
Alan G. B. Lauder and Daqing Wan, Counting points on varieties over finite fields of small characteristic, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 579–612. MR 2467558
A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
Bernard R. McDonald, Finite rings with identity, Pure and Applied Mathematics, Vol. 28, Marcel Dekker, Inc., New York, 1974. MR 0354768
Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An introduction to the theory of numbers, 5th ed., John Wiley & Sons, Inc., New York, 1991. MR 1083765
R. Raghavendran, Finite associative rings, Compositio Math. 21 (1969), 195–229. MR 246905
Ana Sălăgean, Factoring polynomials over $Z_4$ and over certain Galois rings, Finite Fields Appl. 11 (2005), no. 1, 56–70. MR 2111898, DOI 10.1016/j.ffa.2004.05.001
Wolfgang M. Schmidt, Solution trees of polynomial congruences modulo prime powers, Number theory in progress, Vol. 1 (Zakopane-Kościelisko, 1997) de Gruyter, Berlin, 1999, pp. 451–471. MR 1689524
Wolfgang M. Schmidt and C. L. Stewart, Congruences, trees, and $p$-adic integers, Trans. Amer. Math. Soc. 349 (1997), no. 2, 605–639. MR 1340185, DOI 10.1090/S0002-9947-97-01547-X
C. Sircana, Factoring polynomials over $\mathbb {Z}/(n)$, Ph.D. thesis, University of Pisa, Italy, 2016.
Daqing Wan, Algorithmic theory of zeta functions over finite fields, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 551–578. MR 2467557
W. A. Zuniga-Galindo, Computing Igusa’s local zeta functions of univariate polynomials, and linear feedback shift registers, J. Integer Seq. 6 (2003), no. 3, Article 03.3.6, 18. MR 2046406