General  Information
Important Dates
Conference Poster
Organizing Committee
Program and Schedule
Invited Talks
Contributed Talks
Software Exhibitions
Registered Participants
 Call  For
Research Papers
Software Exhibitions
Jenks Prize Nominations
 Local  Information
Conference Location
Speakers' Information
Gastronomic Guide
Additional Information
Social Events
Previous ISSACs
Other Events



Complexity Issues in Bivariate Polynomial Factorization

A. Bostan, G. Lecerf, B. Salvy, E. Schost, B. Wiebelt


Many polynomial factorization algorithms are based on the Hensel lifting and factor recombination scheme. In the case of 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, for the so-called trace recombination approach. 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 often appears to be the practical bottleneck of this method: we propose a new 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.

  issac2004 @