Hensel lifting and bivariate polynomial factorisation over finite fields
HTML articles powered by AMS MathViewer
- by Shuhong Gao and Alan G. B. Lauder PDF
- Math. Comp. 71 (2002), 1663-1676 Request permission
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
- W. S. Brown, On Euclid’s algorithm and the computation of polynomial greatest common divisors, J. Assoc. Comput. Mach. 18 (1971), 478–504. MR 307450, DOI 10.1145/321662.321664
- David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693–701. MR 1129288, DOI 10.1007/BF01178683
- L. Carlitz, “The arithmetic of polynomials in a Galois field”, Amer. J. Math. 54 (1932), 39–50.
- George E. Collins, Factoring univariate integral polynomials in polynomial average time, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 317–329. MR 575695
- Philippe Flajolet, Xavier Gourdon, and Daniel Panario, Random polynomials and polynomial factorization, Automata, languages and programming (Paderborn, 1996) Lecture Notes in Comput. Sci., vol. 1099, Springer, Berlin, 1996, pp. 232–243. MR 1464452, DOI 10.1007/3-540-61440-0_{1}31
- S. Gao, “Absolute irreducibility of polynomials via Newton polytopes,” J. Algebra 237 (2001), 501–520. (Available at URL: http://www.math.clemson.edu/faculty/Gao)
- S. Gao and A. G. B. Lauder, “Decomposition of polytopes and polynomials,” Discrete and Computational Geometry. 26 (2001), 89–104. (Available at URL: http://www.math. clemson.edu/faculty/Gao)
- Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
- K. O. Geddes, S. R. Czapor, and G. Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Boston, MA, 1992. MR 1256483, DOI 10.1007/b102438
- Erich Kaltofen and Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179–1197. MR 1459389, DOI 10.1090/S0025-5718-98-00944-2
- David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 396470, DOI 10.1145/321879.321890
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
- Da Qing Wan, Factoring multivariate polynomials over large finite fields, Math. Comp. 54 (1990), no. 190, 755–770. MR 1011448, DOI 10.1090/S0025-5718-1990-1011448-0
- Paul S. Wang, Factoring multivariate polynomials over algebraic number fields, Math. Comp. 30 (1976), no. 134, 324–336. MR 568283, DOI 10.1090/S0025-5718-1976-0568283-X
- David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 396470, DOI 10.1145/321879.321890
- Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, DOI 10.1016/0022-314X(69)90047-X
Additional Information
- Shuhong Gao
- Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975
- MR Author ID: 291308
- Email: sgao@math.clemson.edu
- Alan G. B. Lauder
- Affiliation: Mathematical Institute, Oxford University, Oxford OX1 3LB, United Kingdom
- Email: lauder@maths.ox.ac.uk
- 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.
- © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 1663-1676
- MSC (2000): Primary 11Y16; Secondary 11T06, 11Y05, 68Q25
- DOI: https://doi.org/10.1090/S0025-5718-01-01393-X
- MathSciNet review: 1933049