Efficiently factoring polynomials modulo p4. (May 2021)

• Record Type: Journal Article
• Authors: Dwivedi, Ashish; Mittal, Rajat; Saxena, Nitin
• Is Part Of: Journal of symbolic computation. Volume 104(2021)
• Page Start: 805
• Page End: 823
• Publication Date: 2021-05
• Subjects: Efficient -- Randomized -- Factor -- Local ring -- Prime-power -- Hensel lift; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.10.001
• Languages: English
• ISSNs: 0747-7171

Abstract

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.