Florida State University Seal

Andy Novocin


Speaker: Andy Novocin
Title: A Recent History of Factoring Polynomials
Affiliation: ENS, Lyon
Date: Friday, February 12, 2010
Place and Time: Room 101, Love Building, 3:35-4:30 pm
Refreshments: Room 204, Love Building, 3:00 pm

Abstract. In this talk we present several algorithms for finding the factorization of a polynomial with integer coefficients. Over the last 25 years there has been an unpleasant dichotomy in such algorithms. Certain algorithms are considered fast in practice and are used in popular Computer Algebra Systems such as MAPLE, MAGMA, SAGE, etc. While a completely different set of algorithms have nice proved bounds on the number of CPU operations needed for termination. Such bounds are needed by theoretical computer scientists for analysis of their own algorithms. The goal of the talk is to arrive at a new algorithm by myself and Mark van Hoeij which resolves this dichotomy. This algorithm has the best proved bounds in the theoretical sense and, as a recent implementation shows, it can be made very practical.