Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Sharp precision in Hensel lifting for bivariate polynomial factorization

Author: Grégoire Lecerf
Journal: Math. Comp. 75 (2006), 921-933
MSC (2000): Primary 12Y05, 68W30; Secondary 11Y16, 12D05, 13P05
Published electronically: January 3, 2006
MathSciNet review: 2197000
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Popularized by Zassenhaus in the seventies, several algorithms for factoring polynomials use a so-called lifting and recombination scheme. Concerning bivariate polynomials, we present a new algorithm for the recombination stage that requires a lifting up to precision twice the total degree of the polynomial to be factored. Its cost is dominated by the computation of reduced echelon solution bases of linear systems. We show that our bound on precision is asymptotically optimal.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 12Y05, 68W30, 11Y16, 12D05, 13P05

Retrieve articles in all journals with MSC (2000): 12Y05, 68W30, 11Y16, 12D05, 13P05

Additional Information

Grégoire Lecerf
Affiliation: Laboratoire de mathématiques (UMR 8100 CNRS), université de Versailles Saint-Quentin-en-Yvelines, 45 avenue des États-Unis, 78035 Versailles, France

Keywords: Polynomial factorization, Hensel lifting
Received by editor(s): May 10, 2004
Received by editor(s) in revised form: February 28, 2005
Published electronically: January 3, 2006
Article copyright: © Copyright 2006 American Mathematical Society

American Mathematical Society