2019/01/20 by Dwivedi, Ashish, Mittal, Rajat, Saxena, Nitin · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.1901.06628
Polynomial factoring has famous practical algorithms over fields-- finite, rational & p-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, x2+p \bmod p2 is irreducible, but x2+px \bmod p2 has exponentially many factors! We present the first randomized poly(deg f, log p) time algorithm to factor a given univariate integral f(x) modulo pk, for a prime p and k ≤ 4. Thus, we solve the open question of factoring modulo p3 posed in (Sircana, ISSAC'17). Our method reduces the general problem of factoring f(x) \bmod pk to that of \em root finding in a related polynomial E(y) \bmod⟨ pk, φ(x)^ℓ ⟩ for some irreducible φ\bmod p. We could efficiently solve the latter for k≤4, by incrementally transforming E(y). Moreover, we discover an efficient and strong generalization of Hensel lifting to lift factors of f(x) \bmod p to those \bmod p4 (if possible). This was previously unknown, as the case of repeated factors of f(x) \bmod p forbids classical Hensel lifting.