License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2019.15
URN: urn:nbn:de:0030-drops-108373
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10837/
Dwivedi, Ashish ;
Mittal, Rajat ;
Saxena, Nitin
Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic 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 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.
BibTeX - Entry
@InProceedings{dwivedi_et_al:LIPIcs:2019:10837,
author = {Ashish Dwivedi and Rajat Mittal and Nitin Saxena},
title = {{Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {15:1--15:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-116-0},
ISSN = {1868-8969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10837},
URN = {urn:nbn:de:0030-drops-108373},
doi = {10.4230/LIPIcs.CCC.2019.15},
annote = {Keywords: deterministic, root, counting, modulo, prime-power, tree, basic irreducible, unramified}
}
|
Keywords: |
|
deterministic, root, counting, modulo, prime-power, tree, basic irreducible, unramified |
|
Collection: |
|
34th Computational Complexity Conference (CCC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
16.07.2019 |
