Document Open Access Logo

Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications

Authors Ashish Dwivedi, Rajat Mittal, Nitin Saxena

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2019.15.pdf
  • Filesize: 0.66 MB
  • 29 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computing methodologies → Representation of mathematical objects
  • Mathematics of computing → Discrete mathematics
  • Theory of computation → Algebraic complexity theory
  • Computing methodologies → Hybrid symbolic-numeric methods
  • Mathematics of computing → Combinatoric problems
  • Computing methodologies → Number theory algorithms
Keywords
  • deterministic
  • root
  • counting
  • modulo
  • prime-power
  • tree
  • basic irreducible
  • unramified

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Finding an irreducible factor, of a polynomial f(x) modulo a prime p, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that counts the number of irreducible factors of f mod p. We can ask the same question modulo prime-powers p^k. The irreducible factors of f mod p^k blow up exponentially in number; making it hard to describe them. Can we count those irreducible factors mod p^k that remain irreducible mod p? These are called basic-irreducible. A simple example is in f=x^2+px mod p^2; it has p many basic-irreducible factors. Also note that, x^2+p mod p^2 is irreducible but not basic-irreducible!
We give an algorithm to count the number of basic-irreducible factors of f mod p^k in deterministic poly(deg(f),k log p)-time. This solves the open questions posed in (Cheng et al, ANTS'18 & Kopp et al, Math.Comp.'19). In particular, we are counting roots mod p^k; which gives the first deterministic poly-time algorithm to compute Igusa zeta function of f. Also, our algorithm efficiently partitions the set of all basic-irreducible factors (possibly exponential) into merely deg(f)-many disjoint sets, using a compact tree data structure and split ideals.

Cite As Get BibTex

Ashish Dwivedi, Rajat Mittal, and Nitin Saxena. Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 15:1-15:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.15

Author Details

Ashish Dwivedi
  • CSE, Indian Institute of Technology, Kanpur, India
Rajat Mittal
  • CSE, Indian Institute of Technology, Kanpur, India
Nitin Saxena
  • CSE, Indian Institute of Technology, Kanpur, India

Acknowledgements

We thank Vishwas Bhargava for introducing us to the open problem of factoring f mod p^3 and the related prime-power questions. A.D. thanks Sumanta Ghosh for the discussions. N.S. thanks the funding support from DST (DST/SJF/MSA-01/2013-14). R.M. would like to thank support from DST through grant DST/INSPIRE/04/2014/001799. We thank anonymous reviewers for their helpful comments and suggestions to improve the introduction section of this paper.

References

  1. Tom M Apostol. Introduction to analytic number theory. Springer Science & Business Media, 2013. Google Scholar
  2. Jérémy Berthomieu, Grégoire Lecerf, and Guillaume Quintin. Polynomial root finding over local rings and application to error correcting codes. Applicable Algebra in Engineering, Communication and Computing, 24(6):413-443, 2013. https://link.springer.com/article/10.1007/s00200-013-0200-5. Google Scholar
  3. Manjul Bhargava. P-orderings and polynomial functions on arbitrary subsets of Dedekind rings. Journal fur die Reine und Angewandte Mathematik, 490:101-128, 1997. Google Scholar
  4. David G Cantor and Daniel M Gordon. Factoring Polynomials over p-Adic Fields. In International Algorithmic Number Theory Symposium, pages 185-208. Springer, 2000. Google Scholar
  5. David G Cantor and Hans Zassenhaus. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation, pages 587-592, 1981. Google Scholar
  6. Qi Cheng, Shuhong Gao, J Maurice Rojas, and Daqing Wan. Counting Roots of Polynomials Over Prime Power Rings. In Thirteenth Algorithmic Number Theory Symposium, ANTS-XIII. Mathematical Sciences Publishers, 2018. URL: http://arxiv.org/abs/1711.01355.
  7. AL Chistov. Efficient factorization of polynomials over local fields. Dokl. Akad. Nauk SSSR, 293(5):1073-1077, 1987. Google Scholar
  8. AL Chistov. Algorithm of polynomial complexity for factoring polynomials over local fields. Journal of mathematical sciences, 70(4):1912-1933, 1994. Google Scholar
  9. M Chojnacka-Pniewska. Sur les congruences aux racines données. In Annales Polonici Mathematici, volume 3, pages 9-12. Instytut Matematyczny Polskiej Akademii Nauk, 1956. Google Scholar
  10. Bruce Dearden and Jerry Metzger. Roots of polynomials modulo prime powers. European Journal of Combinatorics, 18(6):601-606, 1997. Google Scholar
  11. Jan Denef. Report on Igusa’s local zeta function. Astérisque, 730-744(201-203):359-386, 1991. Google Scholar
  12. Jan Denef and Kathleen Hoornaert. Newton polyhedra and Igusa’s local zeta function. Journal of number Theory, 89(1):31-64, 2001. Google Scholar
  13. Ashish Dwivedi, Rajat Mittal, and Nitin Saxena. Efficiently factoring polynomials modulo p⁴. The 44th International Symposium on Symbolic and Algebraic Computation (ISSAC), 2019. URL: https://www.cse.iitk.ac.in/users/nitin/papers/factor-mod-p4.pdf.
  14. Andrzej Ehrenfeucht and Marek Karpinski. The computational complexity of (xor, and)-counting problems. International Computer Science Inst., 1990. Google Scholar
  15. Kurt Hensel. Eine neue Theorie der algebraischen Zahlen. Mathematische Zeitschrift, 2(3):433-452, September 1918. Google Scholar
  16. Jun-ichi Igusa. Complex powers and asymptotic expansions. I. Functions of certain types. Journal für die reine und angewandte Mathematik, 268:110-130, 1974. Google Scholar
  17. Adam Klivans. Factoring polynomials modulo composites. Technical report, Carnegie-Mellon Univ, Pittsburgh PA, Dept of CS, 1997. Google Scholar
  18. Neal Koblitz. P-adic numbers. In p-adic Numbers, p-adic Analysis, and Zeta-Functions, pages 1-20. Springer, 1977. Google Scholar
  19. Leann Kopp, Natalie Randall, Joseph Rojas, and Yuyu Zhu. Randomized polynomial-time root counting in prime power rings. Mathematics of Computation, 2019. URL: https://doi.org/10.1090/mcom/3431.
  20. Alan GB Lauder. Counting solutions to equations in many variables over finite fields. Foundations of Computational Mathematics, 4(3):221-267, 2004. Google Scholar
  21. Rudolf Lidl and Harald Niederreiter. Introduction to finite fields and their applications. Cambridge university press, 1994. Google Scholar
  22. Davesh Maulik. Root sets of polynomials modulo prime powers. Journal of Combinatorial Theory, Series A, 93(1):125-140, 2001. Google Scholar
  23. Bernard R McDonald. Finite rings with identity, volume 28. Marcel Dekker Incorporated, 1974. Google Scholar
  24. Vincent Neiger, Johan Rosenkilde, and Éric Schost. 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, pages 349-356. ACM, 2017. Google Scholar
  25. Ivan Niven, Herbert S Zuckerman, and Hugh L Montgomery. An introduction to the theory of numbers. John Wiley & Sons, 2013. Google Scholar
  26. Ana Sălăgean. Factoring polynomials over ℤ₄ and over certain Galois rings. Finite fields and their applications, 11(1):56-70, 2005. Google Scholar
  27. Adi Shamir. On the generation of multivariate polynomials which are hard to factor. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 796-804. ACM, 1993. Google Scholar
  28. Victor Shoup. A computational introduction to number theory and algebra. Cambridge university press, 2009. Google Scholar
  29. Wacław Sierpiński. Remarques sur les racines d'une congruence. Annales Polonici Mathematici, 1(1):89-90, 1955. Google Scholar
  30. Carlo Sircana. Factorization of Polynomials over ℤ/(pⁿ). In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pages 405-412. ACM, 2017. Google Scholar
  31. Joachim von zur Gathen and Silke Hartlieb. Factorization of polynomials modulo small prime powers. Technical report, Paderborn Univ, 1996. Google Scholar
  32. Joachim von zur Gathen and Silke Hartlieb. Factoring modular polynomials. Journal of Symbolic Computation, 26(5):583-606, 1998. (Conference version in ISSAC'96). Google Scholar
  33. Joachim von zur Gathen and Daniel Panario. Factoring polynomials over finite fields: A survey. Journal of Symbolic Computation, 31(1-2):3-17, 2001. Google Scholar
  34. Hans Zassenhaus. On hensel factorization, I. Journal of Number Theory, 1(3):291-311, 1969. Google Scholar
  35. WA Zuniga-Galindo. Computing Igusa’s local zeta functions of univariate polynomials, and linear feedback shift registers. Journal of Integer Sequences, 6(2):3, 2003. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact