New Recombination Techniques for Polynomial Factorization Algorithms Based on Hensel Lifting

April 18, 2007
  • Polynomials, factorization
  • 12D05
I will present new deterministic and probabilistic recombination algorithms to compute the irreducible factorization of bivariate polynomials via the classical Hensel lifting technique, and for the 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.