Efficiently factoring polynomials modulo \(p^4\) (Q2229745): Difference between revisions

Polynomial factoring over \(\mathbb{Z}_n\), the ring of residue classes modulo \(n\), is a computationally hard problem when \(n\) is a composite number. Many researchers tried to factoring \(f\) modulo \(n\) in some special cases i.e., \(n=p^k\), where \(p\) is a prime and integer \(k\ge2\). \textit{A. Sălăgean} [Finite Fields Appl. 11, No. 1, 56--70 (2005; Zbl 1075.11078)] and \textit{C. Sircana} [in: Proceedings of the 42nd international symposium on symbolic and algebraic computation, ISSAC 2017, Kaiserslautern, Germany, July 25--28, 2017. New York, NY: Association for Computing Machinery (ACM). 405--412 (2017; Zbl 1458.13028)] gave the factoring algorithm for \(k=2\) and \(k=3\) respectively. In this paper, the authors present the first randomized polynomial time algorithm to factor a given univariate polynomial \(f\) modulo \(p^k\), where \(p\) is a prime and \(k\le 4\). They reduce the problem of factoring \(f\in\mathbb{Z}[x]\) modulo \(p^k\) to the problem of finding roots of the univariate polynomial \(E(y)\in(\mathbb{Z}[x])[y]\) modulo a bi-generated ideal \(\langle p^k, \phi(x)^{ak}\rangle\), where \(\phi(x)\in\mathbb{Z}[x]\) is an irreducible polynomial modulo \(p\) such that \(f\equiv \phi^e\mod {p}\) with \(1\le a\le e\) and \(E(y):=f\cdot(\phi^{a(k-1)}+\phi^{a(k-2)}(py)+\cdots+\phi^{a}(py)^{k-2}+(py)^{k-1})\). The authors refine Hensel lifting for \(k\le 4\) by giving possible lifts of a factor of \(f\) modulo \(p\). Finally, they point out the issues in applying their technique to factor \(f\) modulo \(p^5\).