Single-factor lifting and factorization of polynomials over local fields (Q438687): Difference between revisions

Let \(K\) be a local field and let \(f(x)\) be a separable monic polynomial with coefficients in the ring of integers \({\mathcal O}\) of \(K\). The Montes algorithm, described in [\textit{J. Montes}, Newto polygons of higher order and arithmetical applications (Spanish). Doctoral Thesis, Barcelona (1999)], gives a method for computing the factorization of \(f(x)\) into monic irreducible polynomials over \({\mathcal O}\), to any specified precision. In addition, the Montes algorithm computes certain data associated to the various factors \(F(x)\) of \(f(x)\). This auxiliary data facilitates further computations involving \(F(x)\). In this paper the authors describe an algorithm which improves the precision of any specified factor produced by the Montes algorithm. This ``single factor algorithm'' converges quadratically, whereas the Montes algorithm converges linearly. The Montes algorithm is still needed to identify the factors of \(f(x)\) and compute the auxiliary data of these factors before the single factor algorithm can be applied. By combining the single factor algorithm with the Montes algorithm the authors obtain an algorithm for factoring polynomials over a local field which is theoretically more efficient than existing algorithms. The authors have implemented this factorization algorithm using the computer algebra package MAGMA. By applying this implementation to various families of examples the authors demonstrate convincingly that their algorithm is more efficient in practice than existing polynomial factorization implementations [\textit{J. Guàrdia, J. Montes} and \textit{E. Nart}, Trans. Am. Math. Soc. 364, No. 1, 361--416 (2012; Zbl 1252.11091)].