Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Mathematics of Computation
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 Free Access

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

PII: S 0025-5718(06)01810-2
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

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia