## 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**

## Additional Information

**Leann Kopp**- Affiliation: Department of Mathematics, Auburn University, 221 Parker Hall, Auburn, Alabama 36849
- Email: LHK0002@auburn.edu
**Natalie Randall**- Affiliation: Department of Mathematics, Austin College, 900 N. Grand Avenue, Sherman, Texas 75090
- Email: natgrandall@gmail.com
**J. Maurice Rojas**- Affiliation: Department of Mathematics, Texas A&M University, 3368, College Station, Texas 77843-3368
- MR Author ID: 354192
- ORCID: 0000-0002-1657-2674
- Email: rojas@math.tamu.edu
**Yuyu Zhu**- Affiliation: Department of Mathematics, Texas A&M University, 3368, College Station, Texas 77843-3368
- Email: zhuyuyu@math.tamu.edu
- Received by editor(s): September 15, 2018
- Received by editor(s) in revised form: January 4, 2019, and January 19, 2019
- Published electronically: April 9, 2019
- Additional Notes: The first and second authors were partially supported by NSF REU grants DMS-1757872 and DMS-1460766.

The third author is the corresponding author

The third and fourth authors were partially supported by NSF grant CCF-1409020, and NSF REU grants DMS-1757872 and DMS-1460766. - © Copyright 2019 by the authors
- Journal: Math. Comp.
**89**(2020), 373-385 - MSC (2010): Primary 11Y16, 11Y99, 16P10
- DOI: https://doi.org/10.1090/mcom/3431
- MathSciNet review: 4011547