Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
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
Email: Gregoire.Lecerf@math.uvsq.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-06-01810-2
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