Sharp precision in Hensel lifting for bivariate polynomial factorization

Lecerf, Grégoire

doi:10.1090/S0025-5718-06-01810-2

Sharp precision in Hensel lifting for bivariate polynomial factorization
HTML articles powered by AMS MathViewer

by Grégoire Lecerf PDF

Math. Comp. 75 (2006), 921-933 Request permission

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

K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global fields, Manuscript, October 2004.
A. Bostan, G. Lecerf, B. Salvy, É. Schost, and B. Wiebelt, Complexity issues in bivariate polynomial factorization, ISSAC 2004, ACM, New York, 2004, pp. 42–49. MR 2126923, DOI 10.1145/1005285.1005294
Shuhong Gao, Absolute irreducibility of polynomials via Newton polytopes, J. Algebra 237 (2001), no. 2, 501–520. MR 1816701, DOI 10.1006/jabr.2000.8586
S. Gao, Absolute irreducibility of polynomials via Newton polytopes, J. Algebra 237 (2001), no. 2, 501–520.
Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Math. Comp. 72 (2003), no. 242, 801–822. MR 1954969, DOI 10.1090/S0025-5718-02-01428-X
Shuhong Gao and Alan G. B. Lauder, Hensel lifting and bivariate polynomial factorisation over finite fields, Math. Comp. 71 (2002), no. 240, 1663–1676. MR 1933049, DOI 10.1090/S0025-5718-01-01393-X
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
E. Kaltofen, Polynomial factorization: A success story, Proceedings of ISSAC 2003, ACM Press, 2003, pp. 3–4.
G. Lecerf, Improved dense multivariate polynomial factorization algorithms, Manuscript, January 2005.
David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 396470, DOI 10.1145/321879.321890
Harald Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 81–87. MR 1223850, DOI 10.1007/BF01386831
Wolfgang Ruppert, Reduzibilität ebener Kurven, J. Reine Angew. Math. 369 (1986), 167–191 (German). MR 850633, DOI 10.1515/crll.1986.369.167
Wolfgang M. Ruppert, Reducibility of polynomials $f(x,y)$ modulo $p$, J. Number Theory 77 (1999), no. 1, 62–70. MR 1695700, DOI 10.1006/jnth.1999.2381
Tateaki Sasaki, Tomokatsu Saito, and Teruhiko Hilano, Analysis of approximate factorization algorithm. I, Japan J. Indust. Appl. Math. 9 (1992), no. 3, 351–368. MR 1189944, DOI 10.1007/BF03167271
Tateaki Sasaki and Mutsuko Sasaki, A unified method for multivariate polynomial factorizations, Japan J. Indust. Appl. Math. 10 (1993), no. 1, 21–39. MR 1208180, DOI 10.1007/BF03167201
Tateaki Sasaki, Masayuki Suzuki, Miroslav Kolář, and Mutsuko Sasaki, Approximate factorization of multivariate polynomials and absolute irreducibility testing, Japan J. Indust. Appl. Math. 8 (1991), no. 3, 357–375. MR 1137647, DOI 10.1007/BF03167142
A. Storjohann, Algorithms for matrix canonical forms, Ph.D. thesis, ETH, Zürich, 2000, http://www.scg.uwaterloo.ca/˜astorjoh.
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
R. Zippel, Effective polynomial computation, Kluwer Academic Publishers, 1993.