Improved dense multivariate polynomial factorization algorithms
We present new deterministic and probabilistic algorithms that reduce the factorization of dense polynomials from several variables to one variable. The deterministic algorithm runs in sub-quadratic time in the dense size of the input polynomial, and the probabilistic algorithm is softly optimal when the number of variables is at least three. We also investigate the reduction from several to two variables and improve the quantitative version of Bertini's irreducibility theorem. (C) 2007 Elsevier Ltd. All rights reserved.
polynomial factorization bertini's irreducibility theorem hensel lifting