New Recombination Techniques for Polynomial Factorization Algorithms Based on Hensel Lifting

Wednesday, April 18, 2007 - 1:30pm - 2:20pm
EE/CS 3-180
Grégoire Lecerf (Université Versailles/Saint Quentin-en-Yvelines)
I will present new deterministic and probabilistic
algorithms to compute the irreducible factorization of
polynomials via the classical Hensel lifting technique, and for
dense representation model. In bi-degree (dx,
dy) with dy
dx, and whatever the characteristic of the base field is,
these algorithms only require the precision of the lifting to be
dx+1. The cost of the deterministic recombination algorithm
is sub-quadratic in dx dy, and the probabilistic version is
faster by
a factor of dy. At the end, I will explain how these
algorithms can
be adapted to the computation of the absolute factorization,
and how
they extend to more than 2 variables.
MSC Code: