Many polynomial factorization algorithms rely on Hensel lifting and factor recombination. For bivariate polynomials we show that lifting the factors up to a precision  linear  in the total degree of the polynomial to be factored is sufficient to deduce the recombination by linear algebra, using  trace recombination . Then, the total cost of the lifting and the recombination stage is subquadratic in the size of the dense representation of the input polynomial. Lifting is often the practical bottleneck of this method: we propose an algorithm based on a faster multi-moduli computation for univariate polynomials and show that it saves a constant factor compared to the classical multifactor lifting algorithm.
['Alin Bostan', 'Grégoire Lecerf', 'Bruno Salvy', 'Éric Schost', 'Bernd Wiebelt']
Complexity issues in bivariate polynomial factorization