Factoring polynomials over global fields

• DOI: 10.5802/jtnb.655
• Publication Date: 2011-09-13T08:31:36Z
• Authors: Karim Belabas; Mark van Hoeij; Jürgen Klüners; Allan Steel
• Keywords: Univariate; Factoring; Rational number; Natural number

We prove that van Hoeij's original algorithm to factor univariate polynomials over the rationals runs in polynomial time, as well natural variants. In particular, our approach also yields time complexity results for bivariate a finite field.