New Recombination Techniques for Polynomial Factorization Algorithms Based on Hensel Lifting

Thursday, October 26, 2006 - 10:50am - 11:40am
EE/CS 3-180
Grégoire Lecerf (Université Versailles/Saint Quentin-en-Yvelines)
Multivariate polynomial factorization algorithms are necessary ingredients to several tasks in computational algebraic geometry such as prime and primary decompositions. They are also extremely useful in many places where they are not necessary but where they lead to major speedups by splitting problems into several smaller ones.

In this talk I will present recent results concerning the factorization reductions from several to two variables via Bertini's theorem, and then from two to one variable. These reductions are based on the very classical Hensel lifting strategy and new fast recombination devices. Over a prime coefficient field, I will show that the irreducible factorization of a bivariate polynomial of bidegree (m,n) roughly reduces to the factorization of a univariate polynomial of degree n, a Hensel lifting to precision m+1, and O~( m n^2 ) arithmetic operations to recombine the lifted factors.

Finally we will report on practical performances of the new algorithms, and on comparisons with other software.
MSC Code: