Factoring polynomials over global fields
Karim Belabas, Mark van Hoeij, Jürgen Klüners, Allan K. Steel · Journal de Théorie des Nombres de Bordeaux · 2009
We prove that van Hoeij’s original algorithm to factor univariate polynomials over the rationals runs in polynomial time, as well as natural variants. In particular, our approach also yields polynomial time complexity results for bivariate polynomials over a finite field.