Mathematics of Computation

Author(s): Shuhong Gao; Alan G. B. Lauder.
Journal: Math. Comp. 71 (2002), 1663-1676.
MSC (2000): Primary 11Y16; Secondary 11T06, 11Y05, 68Q25
Posted: December 5, 2001
Retrieve article in: PDF
This article is available free of charge

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.

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: http://www.math.clemson.edu/faculty/Gao)
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. clemson.edu/faculty/Gao)
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

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

Shuhong Gao
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975
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

DOI: 10.1090/S0025-5718-01-01393-X
PII: S 0025-5718(01)01393-X
Keywords: Bivariate polynomial, finite field, Hensel lifting, factorisation, average-case complexity
Received by editor(s): June 6, 2000
Posted: 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 of article: Copyright 2001, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS