|
Sharp precision in Hensel lifting for bivariate polynomial factorization
Author(s):
Grégoire
Lecerf.
Journal:
Math. Comp.
75
(2006),
921-933.
MSC (2000):
Primary 12Y05, 68W30;
Secondary 11Y16, 12D05, 13P05
Posted:
January 3, 2006
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
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:
-
- 1.
- K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global fields, Manuscript, October 2004.
- 2.
- A. Bostan, G. Lecerf, B. Salvy, É. Schost, and B. Wiebelt, Complexity issues in bivariate polynomial factorization, Proceedings of ISSAC 2004, ACM Press, 2004, pp. 42-49. MR 2126923
MR 1440179 (99c:68002) - 3.
- P. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, 1997. MR 1816701 (2002f:52013)
- 4.
- S. Gao, Absolute irreducibility of polynomials via Newton polytopes, J. Algebra 237 (2001), no. 2, 501-520.
- 5.
- -, Factoring multivariate polynomials via partial differential equations, Math. Comp. 72 (2003), 801-822. MR 1954969 (2003m:12014)
- 6.
- S. Gao and A. G. B. Lauder, Hensel lifting and bivariate polynomial factorisation over finite fields, Math. Comp. 71 (2002), no. 240, 1663-1676. MR 1933049 (2003j:11149)
- 7.
- J. von zur Gathen and J. Gerhard, Modern computer algebra, second ed., Cambridge University Press, 2003. MR 2001757 (2004g:68202)
- 8.
- E. Kaltofen, Polynomial factorization: A success story, Proceedings of ISSAC 2003, ACM Press, 2003, pp. 3-4.
- 9.
- G. Lecerf, Improved dense multivariate polynomial factorization algorithms, Manuscript, January 2005.
- 10.
- D. R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291-308. MR 0396470 (53:335a)
- 11.
- H. 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 (94h:11112)
- 12.
- W. M. Ruppert, Reduzibilität ebener Kurven, J. Reine Angew. Math. 369 (1986), 167-191. MR 0850633 (88j:14010)
- 13.
- -, Reducibility of polynomials
 modulo  , J. Number Theory 77 (1999), no. 1, 62-70. MR 1695700 (2000d:11128) - 14.
- T. Sasaki, T. Saito, and T. Hilano, Analysis of approximate factorization algorithm. I, Japan J. Indust. Appl. Math. 9 (1992), no. 3, 351-368. MR 1189944 (94a:12002)
- 15.
- T. Sasaki and M. Sasaki, A unified method for multivariate polynomial factorizations, Japan J. Indust. Appl. Math. 10 (1993), no. 1, 21-39. MR 1208180 (94a:13029)
- 16.
- T. Sasaki, M. Suzuki, M. Kolár, and M. Sasaki, Approximate factorization of multivariate polynomials and absolute irreducibility testing, Japan J. Indust. Appl. Math. 8 (1991), no. 3, 357-375. MR 1137647 (92j:12002)
- 17.
- A. Storjohann, Algorithms for matrix canonical forms, Ph.D. thesis, ETH, Zürich, 2000, http://www.scg.uwaterloo.ca/~astorjoh.
- 18.
- P. S. Wang, An improved multivariate polynomial factoring algorithm, Math. Comp. 32 (1978), no. 144, 1215-1231. MR 0568284 (58:27887b)
- 19.
- P. S. Wang and L. P. Rothschild, Factoring multivariate polynomials over the integers, Math. Comp. 29 (1975), 935-950. MR 0396471 (53:335b)
- 20.
- H. Zassenhaus, On Hensel factorization I, J. Number Theory 1 (1969), no. 1, 291-311. MR 0242793 (39:4120)
- 21.
- R. Zippel, Effective polynomial computation, Kluwer Academic Publishers, 1993.
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(2000):
12Y05, 68W30,
11Y16, 12D05, 13P05
Retrieve articles in all Journals with MSC
(2000):
12Y05, 68W30,
11Y16, 12D05, 13P05
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
DOI:
10.1090/S0025-5718-06-01810-2
PII:
S 0025-5718(06)01810-2
Keywords:
Polynomial factorization,
Hensel lifting
Received by editor(s):
May 10, 2004
Received by editor(s) in revised form:
February 28, 2005
Posted:
January 3, 2006
Copyright of article:
Copyright
2006,
American Mathematical Society
|
Comments: webmaster@ams.org