ECCC-Report TR19-008https://eccc.weizmann.ac.il/report/2019/008Comments and Revisions published for TR19-008en-usSun, 20 Jan 2019 11:00:53 +0200
Paper TR19-008
| Efficiently factoring polynomials modulo $p^4$ |
Ashish Dwivedi,
Rajat Mittal,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2019/008Polynomial 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, $x^2+p \bmod p^2$ is irreducible, but $x^2+px \bmod p^2$ 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 $p^k$, for a prime $p$ and $k \leq 4$. 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(x) \bmod p^k$ to that of {\em root finding} in a related polynomial $E(y) \bmod\langle p^k, \varphi(x)^\ell \rangle$ for some irreducible $\varphi \bmod p$. We could efficiently solve the latter for $k\le4$, 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\ p^4$ (if possible). This was previously unknown, as the case of repeated factors of $f(x) \bmod p$ forbids classical Hensel lifting.Sun, 20 Jan 2019 11:00:53 +0200https://eccc.weizmann.ac.il/report/2019/008