The complexity of factoring univariatepolynomials over the rationals
Mark van Hoeij · 2013
This tutorial will explain the algorithm behind the currently fastest implementations for univariate factorization over the rationals. The complexity will be analyzed; it turns out that modifications were needed in order to prove a polynomial time complexity while preserving the best practical performance.