2026-07-24T03:39:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10837 2024-03-06T10:46:50Z ddc:004 open_access

Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications Dwivedi, Ashish Mittal, Rajat Saxena, Nitin deterministic root counting modulo prime-power tree basic irreducible unramified 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ashish Dwivedi and Rajat Mittal and Nitin Saxena 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.15 urn:nbn:de:0030-drops-108373 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.15 eng https://creativecommons.org/licenses/by/3.0/legalcode