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?)

  • 1. W. S. BROWN, ``On Euclid's algorithm and the computation of polynomial greatest common divisors'', J. ACM 18 (1971), 478-504. MR 46:6570
  • 2. D.G. CANTOR AND E. KALTOFEN, ``On fast multiplication of polynomials over arbitrary algebras'', Acta Inform. 28 (1991), 693-701. MR 92i:68068
  • 3. L. CARLITZ, ``The arithmetic of polynomials in a Galois field'', Amer. J. Math. 54 (1932), 39-50.
  • 4. G. E. COLLINS, ``Factoring univariate integral polynomials in polynomial average time'', Symbolic and algebraic computation (EUROSAM '79, Internat. Sympos., Marseille, 1979), pp. 317-329, Lecture Notes in Comput. Sci., 72, Springer, Berlin-New York, 1979. MR 81g:68064
  • 5. P. FLAJOLET, X. GOURDON AND D. PANARIO, ``Random polynomials and polynomial factorization'', Automata, languages and programming (Paderborn, 1996), 232-243, Lecture Notes in Comput. Sci., 1099, Springer, Berlin, 1996. MR 98e:68123
  • 6. S. GAO, ``Absolute irreducibility of polynomials via Newton polytopes,'' J. Algebra 237 (2001), 501-520. CMP 2001:09 (Available at URL:
  • 7. S. GAO AND A. G. B. LAUDER, ``Decomposition of polytopes and polynomials,'' Discrete and Computational Geometry. 26 (2001), 89-104. CMP 2001:13 (Available at URL: http://www.math.
  • 8. J. VON ZUR GATHEN AND V. SHOUP, ``Computing Frobenius maps and factoring polynomials'', Computational Complexity 2 (1992), 187-224. MR 94d:12011
  • 9. K. O. GEDDES, S. R. CZAPOR AND G. LABAHN, Algorithms for Computer Algebra, Kluwer, Boston/Dordrecht/London, 1992. MR 96a:68049
  • 10. E. KALTOFEN AND V. SHOUP, ``Subquadratic-time factoring of polynomials over finite fields'', Math. Comp. 67 (1998), no. 223, 1179-1197. MR 99m:68097
  • 11. D.R. MUSSER, ``Multivariate polynomial factorization'', J. ACM 22 (1975), 291-308. MR 53:335a
  • 12. A. SCH¨ONHAGE AND V. STRASSEN, ``Schnelle Multiplikation großer Zahlen'', Computing 7 (1971), 281-292. MR 45:1431
  • 13. D. WAN, ``Factoring polynomials over large finite fields'', Math. Comp. 54 (1990), No. 190, 755-770. MR 90i:11141
  • 14. P. S. WANG, ``An improved multivariate polynomial factorization algorithm'', Math. Comp. 32 (1978), 1215-1231. MR 58:27887b
  • 15. P. S. WANG AND L. P. ROTHSCHILD, ``Factoring multivariate polynomials over the integers,'' Math. Comp. 29 (1975), 935-950. MR 53:335b
  • 16. H. ZASSENHAUS, ``On Hensel factorization I'', J. Number Theory 1 (1969), 291-311. MR 39:4120

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

American Mathematical Society