Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Hensel lifting and bivariate polynomial factorisation over finite fields

Authors: Shuhong Gao and Alan G. B. Lauder
Journal: Math. Comp. 71 (2002), 1663-1676
MSC (2000): Primary 11Y16; Secondary 11T06, 11Y05, 68Q25
Published electronically: December 5, 2001
MathSciNet review: 1933049
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents an average time analysis of a Hensel lifting based factorisation algorithm for bivariate polynomials over finite fields. It is shown that the average running time is almost linear in the input size. This explains why the Hensel lifting technique is fast in practice for most polynomials.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11T06, 11Y05, 68Q25

Retrieve articles in all journals with MSC (2000): 11Y16, 11T06, 11Y05, 68Q25

Additional Information

Shuhong Gao
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975

Alan G. B. Lauder
Affiliation: Mathematical Institute, Oxford University, Oxford OX1 3LB, United Kingdom

Keywords: Bivariate polynomial, finite field, Hensel lifting, factorisation, average-case complexity
Received by editor(s): June 6, 2000
Published electronically: December 5, 2001
Additional Notes: The first author was supported in part by NSF grant #DMS9970637, NSA grant #MDA904-00-1-0048 and ONR grant #N00014-00-1-0565. The second author gratefully acknowledges the support of the Marr Educational Trust and Wolfson College, Oxford.
Article copyright: © Copyright 2001 American Mathematical Society