Modular Las Vegas algorithms for polynomial absolute factorization (Q607052)

The authors provide a Las Vegas absolute irreducibility test of integer polynomials based on Newton polytopes: based on a sufficient criterion for absolute irreducibility, reduction modulo primes is done to improve the shape of the polygon so that the condition can be satisfied. Then, following the same strategy of the test, an absolute factorization algorithm is given. This involves the computation of a minimal field extension containing the coefficients of one factor (in particular, the minimal polynomial of a primitive element, via LLL), in contrast with the TKTD algorithm [\textit{R. Dvornicich} and \textit{C. Traverso}, ``Newton symmetric functions and the arithmetic of algebraically closed fields'', Applied algebra, algebraic algorithms and error-correcting codes, Proc. 5th Int. Conference, AAECC-5, Menorca, Spain, 1987, Lect. Notes Comput. Sci. 356, 216--224 (1989; Zbl 0689.12014)], [\textit{E. Kaltofen}, ``Fast parallel absolute irreducibility testing'', J. Symb. Comput. 1, 57--67 (1985; Zbl 0599.68038)] and [\textit{B. Trager}, On the integration of algebraic functions. Ph.D. Thesis (1985)] where a larger degree extension is used in general. Hensel lifting is required at the end of the algorithm, although a parallel version is suggested where Lagrange interpolations are performed instead. Detailed speed tests show good practical performance.