Efficiently factoring polynomials modulo p⁴

Abstract

Polynomial factoring has famous practical algorithms over fields– finite, rational and p-adic. However, modulo prime powers, factoring gets harder because there is non-unique factorization and a combinatorial blowup ensues. For example, x²+pmodp2 is irreducible, but x²+pxmodp² has exponentially many factors in the input size (which here is logarithmic in p)! We present the first randomized poly(deg⁡f,log⁡p) time algorithm to factor a given univariate integral polynomial f modulo pk, for a prime p and k≤4.1 Thus, we solve the open question of factoring modulo p³ posed in (Sircana, ISSAC'17). Our method reduces the general problem of factoring fmodpk to that of root finding of a related polynomial E(y)mod〈pk,φ(x)ℓ〉 for some irreducible φmodp. We can efficiently solve the latter for k≤4, by incrementally transforming E. Moreover, we discover an efficient refinement of Hensel lifting to lift factors of fmodp to those modp⁴ (if possible). This was previously unknown, as the case of repeated factors of fmodp forbids classical Hensel lifting.