Dwivedi, Ashish ;
Mittal, Rajat ;
Saxena, Nitin
Counting BasicIrreducible Factors Mod p^k in Deterministic PolyTime and pAdic Applications
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 primepowers 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 basicirreducible. A simple example is in f=x^2+px mod p^2; it has p many basicirreducible factors. Also note that, x^2+p mod p^2 is irreducible but not basicirreducible!
We give an algorithm to count the number of basicirreducible 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 polytime algorithm to compute Igusa zeta function of f. Also, our algorithm efficiently partitions the set of all basicirreducible factors (possibly exponential) into merely deg(f)many disjoint sets, using a compact tree data structure and split ideals.
BibTeX  Entry
@InProceedings{dwivedi_et_al:LIPIcs:2019:10837,
author = {Ashish Dwivedi and Rajat Mittal and Nitin Saxena},
title = {{Counting BasicIrreducible Factors Mod p^k in Deterministic PolyTime and pAdic Applications}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {15:115:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10837},
URN = {urn:nbn:de:0030drops108373},
doi = {10.4230/LIPIcs.CCC.2019.15},
annote = {Keywords: deterministic, root, counting, modulo, primepower, tree, basic irreducible, unramified}
}
2019
Keywords: 

deterministic, root, counting, modulo, primepower, tree, basic irreducible, unramified 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 