Factorization of polynomials by transcendental evaluation

van der Hulst, M.-P.Lenstra, Arjen K.2010-06-242010-06-242010-06-24198510.1007/3-540-15984-3_246https://infoscience.epfl.ch/handle/20.500.14299/51011A new polynomial-time algorithm for the factorization of polynomials in two variables with rational coefficients is presented. The algorithm works by replacing one of the variables by an approximation of a transcendental number. It generalizes recent results by Kannan, Lenstra, Lovasz and Schonhage. Asymptotically the algorithm improves on the running times of previously published methodsapproximation theorypolynomialsFactorization of polynomials by transcendental evaluationtext::conference output::conference proceedings::conference paper