Sayak Chakrabarti
ABSTRACT
Finding roots of a bivariate polynomial f(x1, x2), over a prime field , is a fundamental question with a long history and several practical algorithms are now known. Effective algorithms for describing the roots modulo pk, k ≥ 2, for any general bivariate polynomial, were unknown until the present paper. The main obstruction is lifting the singular roots to . Such roots may be numerous and behave unpredictably, i.e., they may or may not lift from to .
We give the first algorithm to describe the roots of a bivariate polynomial over in a practical way. Notably, when the degree of the polynomial is constant, our algorithm runs in deterministic time which is polynomial in p + k. This is a significant improvement over brute force, which would require exploring p2k possible values. Our method also gives the first efficient algorithms for the following problems (which were also open): (1) efficiently representing all the (possibly infinitely-many) p-adic roots, and (2) computing the underlying Igusa’s local zeta function. We also obtain a new, effective method to prove the rationality of this zeta function.
- Elwyn R Berlekamp. 1967. Factoring polynomials over finite fields. Bell System Technical Journal 46, 8 (1967), 1853–1859.Google Scholar
Cross Ref
- Elwyn R Berlekamp. 1970. Factoring polynomials over large finite fields. Mathematics of computation 24, 111 (1970), 713–735.Google Scholar
- Jérémy Berthomieu, Grégoire Lecerf, and Guillaume Quintin. 2013. Polynomial root finding over local rings and application to error correcting codes. Applicable Algebra in Engineering, Communication and Computing 24, 6 (2013), 413–443.Google ScholarCross Ref
- BJ Birch and K McCann. 1967. A Criterion for the p-adic Solubility of Diophantine Equations. The Quarterly Journal of Mathematics 18, 1 (1967), 59–63.Google ScholarCross Ref
- Andreas Björklund, Petteri Kaski, and Ryan Williams. 2019. Solving systems of polynomial equations over GF (2) by a parity-counting self-reduction. In 46th International Colloquium on Automata, Languages, and Programming (ICALP), 2019, Patras, Greece(LIPIcs, Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 26:1–26:13.Google Scholar
- David G. Cantor and Daniel M. Gordon. 2000. Factoring Polynominals over p-Adic Fields. In Algorithmic Number Theory, 4th International Symposium, ANTS-IV, Leiden, Netherlands(Lecture Notes in Computer Science, Vol. 1838). Springer, 185–208.Google Scholar
- David G Cantor and Hans Zassenhaus. 1981. A new algorithm for factoring polynomials over finite fields. Math. Comp. 36, 154 (1981), 587–592.Google ScholarCross Ref
- Sayak Chakrabarti. 2022. Multivariate polynomials modulo prime powers: their roots, zeta-function and applications. Master’s thesis. CSE, IIT Kanpur, India.Google Scholar
- Sayak Chakrabarti, Ashish Dwivedi, and Nitin Saxena. 2022. Solving polynomial systems over non-fields and applications to modular polynomial factoring. Technical Report. CSE, IIT Kanpur.Google Scholar
- Sayak Chakrabarti and Nitin Saxena. 2022. An effective description of the roots of multivariates mod pk and the related Igusa’s local zeta function. Technical Report. CSE, IIT Kanpur.Google Scholar
- Howard Cheng and George Labahn. 2001. Computing all factorizations in Zn[x]. In Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation (ISSAC), Ontario, Canada. ACM, 64–71.Google ScholarDigital Library
- Qi Cheng, Shuhong Gao, J Maurice Rojas, and Daqing Wan. 2019. Counting roots for polynomials modulo prime powers. The Open Book Series 2, 1 (2019), 191–205.Google Scholar
- Qi Cheng, J Maurice Rojas, and Daqing Wan. 2020. Computing zeta functions of large polynomial systems over finite fields. arXiv preprint arXiv:2007.13214 (2020), 1–10.Google Scholar
- Alexander Leonidovich Chistov. 1987. Efficient factorization of polynomials over local fields. Doklady Akademii Nauk 293, 5 (1987), 1073–1077.Google Scholar
- Alexander L Chistov. 2021. An Effective Algorithm for Deciding Solvability of a System of Polynomial Equations over p -adic Integers. Algebra i Analiz 33, 6 (2021), 162–196.Google Scholar
- David Cox, John Little, and Donal O’Shea. 2013. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media.Google Scholar
- Bruce Dearden and Jerry Metzger. 1997. Roots of polynomials modulo prime powers. European Journal of Combinatorics 18, 6 (1997), 601–606.Google ScholarDigital Library
- Jan Denef. 1984. The rationality of the Poincaré series associated to the p-adic points on a variety. Invent. math 77, 1 (1984), 1–23.Google Scholar
- Jan Denef and Kathleen Hoornaert. 2001. Newton polyhedra and Igusa’s local zeta function. Journal of number Theory 89, 1 (2001), 31–64.Google ScholarCross Ref
- Ashish Dwivedi. 2023. Polynomials over composites: Compact root representation via ideals and algorithmic consequences. Ph. D. Dissertation. CSE, IIT Kanpur, India.Google Scholar
- Ashish Dwivedi, Rajat Mittal, and Nitin Saxena. 2019. Counting Basic-Irreducible Factors Mod pk in Deterministic Poly-Time and p-Adic Applications. In Proceedings of 34th Computational Complexity Conference (CCC 2019). Springer, 15:1–15:29.Google ScholarDigital Library
- Ashish Dwivedi, Rajat Mittal, and Nitin Saxena. 2021. Efficiently factoring polynomials modulo p4. Journal of Symbolic Computation 104 (2021), 805–823.Google ScholarCross Ref
- Ashish Dwivedi and Nitin Saxena. 2020. Computing Igusa’s local zeta function of univariates in deterministic polynomial-time. Open Book Series 4, 1 (2020), 197–214.Google Scholar
- Andrzej Ehrenfeucht and Marek Karpinski. 1990. The computational complexity of (xor, and)-counting problems. International Computer Science Inst.Google Scholar
- Pierrick Gaudry and Robert Harley. 2000. Counting points on hyperelliptic curves over finite fields. In International Algorithmic Number Theory Symposium. Springer, 313–332.Google ScholarCross Ref
- Parikshit Gopalan, Venkatesan Guruswami, and Richard J Lipton. 2008. Algorithms for modular counting of roots of multivariate polynomials. Algorithmica 50, 4 (2008), 479–496.Google ScholarDigital Library
- Jordi Guàrdia, Enric Nart, and Sebastian Pauli. 2012. Single-factor lifting and factorization of polynomials over local fields. Journal of Symbolic Computation 47, 11 (2012), 1318–1346.Google ScholarDigital Library
- Aditya Gulati, Sayak Chakrabarti, and Rajat Mittal. 2021. On Algorithms to Find p-ordering. In Conference on Algorithms and Discrete Applied Mathematics. Springer, 333–345.Google ScholarDigital Library
- David Harvey. 2015. Computing zeta functions of arithmetic schemes. Proceedings of the London Mathematical Society 111, 6 (2015), 1379–1401.Google ScholarCross Ref
- Kurt Hensel. 1918. Eine neue Theorie der algebraischen Zahlen. Mathematische Zeitschrift 2, 3 (1918), 433–452.Google ScholarCross Ref
- M-D Huang and Y-C Wong. 1999. Solvability of systems of polynomial congruences modulo a large prime. computational complexity 8, 3 (1999), 227–257.Google Scholar
- Jun-ichi Igusa. 1974. Complex powers and asymptotic expansions. I. Functions of certain types.Journal für die reine und angewandte Mathematik 0268_0269 (1974), 110–130. http://eudml.org/doc/151455Google Scholar
- Jun-Ichi Igusa. 1977. Some observations on higher degree characters. American Journal of Mathematics 99, 2 (1977), 393–417.Google ScholarCross Ref
- Jun-ichi Igusa. 2007. An introduction to the theory of local zeta functions. Vol. 14. American Mathematical Soc.Google Scholar
- Erich Kaltofen. 1982. A polynomial-time reduction from bivariate to univariate integral polynomial factorization. In 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982). IEEE, 57–64.Google ScholarDigital Library
- Erich Kaltofen. 1985. Polynomial-time reductions from multivariate to bi-and univariate integral polynomial factorization. SIAM J. Comput. 14, 2 (1985), 469–489.Google ScholarDigital Library
- Neeraj Kayal. 2005. Solvability of a system of bivariate polynomial equations over a finite field. In International Colloquium on Automata, Languages, and Programming. Springer, 551–562.Google Scholar
- Kiran S Kedlaya. 2001. Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology. Journal of the Ramanujan Mathematical Society 16, 4 (2001), 323–338.Google Scholar
- Kiran S Kedlaya. 2004. Computing zeta functions via p-adic cohomology. In International Algorithmic Number Theory Symposium. Springer, 1–17.Google ScholarCross Ref
- Kiran S Kedlaya and Christopher Umans. 2011. Fast polynomial factorization and modular composition. SIAM J. Comput. 40, 6 (2011), 1767–1802.Google ScholarDigital Library
- Leann Kopp, Natalie Randall, Joseph Rojas, and Yuyu Zhu. 2020. Randomized polynomial-time root counting in prime power rings. Math. Comp. 89, 321 (2020), 373–385.Google ScholarCross Ref
- Alan GB Lauder. 2006. A recursive method for computing zeta functions of varieties. LMS Journal of Computation and Mathematics 9 (2006), 222–269.Google ScholarCross Ref
- Frank Lehmann, Markus Maurer, Volker Müller, and Victor Shoup. 1994. Counting the number of points on elliptic curves over finite fields of characteristic greater than three. In International Algorithmic Number Theory Symposium. Springer, 60–70.Google ScholarCross Ref
- Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, Ryan Williams, and Huacheng Yu. 2017. Beating brute force for systems of polynomial equations over finite fields. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2190–2202.Google ScholarCross Ref
- Kazuto Matsuo, Jinhui Chao, and Shigeo Tsujii. 2002. An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields. In International Algorithmic Number Theory Symposium. Springer, 461–474.Google ScholarCross Ref
- Davesh Maulik. 2001. Root sets of polynomials modulo prime powers. Journal of Combinatorial Theory, Series A 93, 1 (2001), 125–140.Google ScholarDigital Library
- Alfred J Menezes, Scott A Vanstone, and Robert J Zuccherato. 1993. Counting points on elliptic curves over . Mathematics of computation 60, 201 (1993), 407–420.Google Scholar
- Vincent Neiger, Johan Rosenkilde, and Éric Schost. 2017. Fast computation of the roots of polynomials over the ring of power series. In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation. 349–356.Google ScholarDigital Library
- Peter N Panayi. 1995. Computation of Leopoldt’s P-adic regulator.Ph. D. Dissertation. University of East Anglia, Norwich, England.Google Scholar
- Caleb Robelle, J Maurice Rojas, and Yuyu Zhu. 2021. Sub-Linear Point Counting for Variable Separated Curves over Prime Power Rings. arXiv preprint arXiv:2102.01626 (2021), 18.Google Scholar
- Lajos Rónyai. 1987. Factoring polynomials over finite fields. In 28th Annual Symposium on Foundations of Computer Science (FOCS 1987). IEEE, 132–137.Google ScholarDigital Library
- Ana Sălăgean. 2005. Factoring polynomials over Z4 and over certain Galois rings. Finite fields and their applications 11, 1 (2005), 56–70.Google Scholar
- Takakazu Satoh. 2002. On p-adic point counting algorithms for elliptic curves over finite fields. In International Algorithmic Number Theory Symposium. Springer, 43–66.Google ScholarCross Ref
- René Schoof. 1995. Counting points on elliptic curves over finite fields. Journal de théorie des nombres de Bordeaux 7, 1 (1995), 219–254.Google ScholarCross Ref
- Carlo Sircana. 2017. Factorization of polynomials over . In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation. 405–412.Google ScholarDigital Library
- Hans Zassenhaus. 1969. On hensel factorization, I. Journal of Number Theory 1, 3 (1969), 291–311.Google ScholarCross Ref
- Hans Zassenhaus. 1978. A remark on the Hensel factorization method. Math. Comp. 32, 141 (1978), 287–292.Google ScholarCross Ref
- Yuyu Zhu. 2020. Trees, point counting beyond fields, and root separation. Ph. D. Dissertation. Texas A&M University, USA.Google Scholar
- WA Zuniga-Galindo. 2003. Computing Igusa’s local zeta functions of univariate polynomials, and linear feedback shift registers. Journal of Integer Sequences 6 (2003), 36.Google Scholar
Index Terms
- An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
Recommendations
Summation and recurrence formula involving the central factorial numbers and zeta function
In this paper, we establish some summation formulas involving the central factorial numbers and zeta function, and prove some recurrence formulas for zeta function.
Applications of the Cosecant and Related Numbers
Power series expansions for cosecant and related functions together with a vast number of applications stemming from their coefficients are derived here. The coefficients for the cosecant expansion can be evaluated by using: (1) numerous recurrence ...
Bartholdi zeta functions of graph coverings
We give a decomposition formula for the Bartholdi zeta function of a regular covering of a graph G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we obtain a decomposition formula for the Bartholdi ...
Comments