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.
Additional Information
- Grégoire Lecerf
- Affiliation: Laboratoire de mathématiques (UMR 8100 CNRS), université de Versailles Saint-Quentin-en-Yvelines, 45 avenue des États-Unis, 78035 Versailles, France
- Email: Gregoire.Lecerf@math.uvsq.fr
- Received by editor(s): May 10, 2004
- Received by editor(s) in revised form: February 28, 2005
- Published electronically: January 3, 2006
- © Copyright 2006 American Mathematical Society
- Journal: Math. Comp. 75 (2006), 921-933
- MSC (2000): Primary 12Y05, 68W30; Secondary 11Y16, 12D05, 13P05
- DOI: https://doi.org/10.1090/S0025-5718-06-01810-2
- MathSciNet review: 2197000