Efficiently factoring polynomials modulo p4. (May 2021) - Dwivedi, Ashish; Mittal, Rajat; Saxena, Nitin
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 2 + p mod p 2 is irreducible, but x 2 + p x mod p 2 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 p k, for a prime p and k ≤ 4 . 1 Thus, we solve the open question of factoring modulo p 3 posed in (Sircana, ISSAC'17). Our method reduces the general problem of factoring f mod p k to that of root finding of a related polynomial E ( y ) mod 〈 p k, φ ( x ) ℓ 〉 for some irreducible φ mod p . 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 f mod p to those mod p 4 (if possible). This was previously unknown, as the case of repeated factors of f mod p forbids classical Hensel lifting.