Complexity issues in bivariate polynomial factorization

ABSTRACT

Many polynomial factorization algorithms rely on Hensel lifting and factor recombination. For bivariate polynomials we show that lifting the factors up to a precision linear in the total degree of the polynomial to be factored is sufficient to deduce the recombination by linear algebra, using trace recombination. Then, the total cost of the lifting and the recombination stage is subquadratic in the size of the dense representation of the input polynomial. Lifting is often the practical bottleneck of this method: we propose an algorithm based on a faster multi-moduli computation for univariate polynomials and show that it saves a constant factor compared to the classical multifactor lifting algorithm.

REFERENCES

• 1: K. Belabas, M. van Hoeij, J. Klüuners, and A. Steel. Factoring polynomials over global fields. 2003.
• 2: Laurent Bernardin, On bivariate Hensel and its parallelization, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.96-100, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281567]
• 3: D. J. Bernstein. Fast multiplication and its applications. Manuscript, 2003.
• 4: A. Bostan , G. Lecerf , É. Schost, Tellegen's principle into practice, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.37-44, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860870]
• 5: A. Bostan, B. Salvy, and É. Schost. Fast algorithms for zero-dimensional polynomial systems using duality. AAECC, 14(4):239--272, 2003.
• 6: P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory. Springer, Berlin, 1997.
• 7: Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003 [doi>10.1090/S0025-5718-02-01428-X]
• 8: J. von zur Gathen. Hensel and Newton methods in valuation rings. Math. Comp., 42(166):637--661, 1984.
• 9: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 10: Joachim von zur Gathen , Erich Kaltofen, Factoring sparse multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.265-287, Sept. 1985 [doi>10.1016/0022-0000(85)90044-3]
• 11: J. von zur Gathen and E. Kaltofen. Factorization of multivariate polynomials over finite fields. Math. Comp., 45:251--261, 1985.
• 12: Guillaume Hanrot , Michel Quercia , Paul Zimmermann, The Middle Product Algorithm I, Applicable Algebra in Engineering, Communication and Computing, v.14 n.6, p.415-438, March 2004 [doi>10.1007/s00200-003-0144-2]
• 13: M. van Hoeij. Factoring polynomials and the knapsack problem. J. Number Theory, 95(2):167--189, 2002.
• 14: E. Kaltofen. Polynomial factorization. In B. Buchberger, G. Collins, and R. Loos, editors, Computer algebra, pages 95--113. Springer, 1982.
• 15: Erich Kaltofen, Sparse Hensel Lifting, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.4-17, April 01-03, 1985
• 16: E. Kaltofen. Factorization of polynomials given by straight-line programs. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 375--412. JAI, 1989.
• 17: Erich Kaltofen, Polynomial factorization: a success story, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.3-4, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860857]
• 18: Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
• 19: Grégoire Lecerf, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Journal of Complexity, v.19 n.4, p.564-596, August 2003 [doi>10.1016/S0885-064X(03)00031-1]
• 20: A. K. Lenstra. Factoring multivariate polynomials over finite fields. J. Comput. System Sci., 2:235--248, 1985.
• 21: David R. Musser, Multivariate Polynomial Factorization, Journal of the ACM (JACM), v.22 n.2, p.291-308, April 1975 [doi>10.1145/321879.321890]
• 22: K. Nagasaka and T. Sasaki. Approximate multivariate polynomial factorization and its time complexity, 1998. preprint.
• 23: Masayuki Noro , Kazuhiro Yokoyama, Yet another practical implementation of polynomial factorization over finite fields, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.200-206, July 07-10, 2002, Lille, France [doi>10.1145/780506.780532]
• 24: T. Sasaki, T. Saito, and T. Hilano. Analysis of approximate factorization algorithm. I. Japan J. Indust. Appl. Math., 9(3):351--368, 1992.
• 25: T. Sasaki and M. Sasaki. A unified method for multivariate polynomial factorizations. Japan J. Indust. Appl. Math., 10(1):21--39, 1993.
• 26: T. Sasaki, M. Suzuki, M. Kolář, and M. Sasaki. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. Indust. Appl. Math., 8(3):357--375, 1991.
• 27: V. Shoup. NTL: A library for doing number theory. http://www.shoup.net.
• 28: A. Storjohann. Algorithms for matrix canonical forms. PhD thesis, ETH, Zürich, 2000.
• 29: P. S. Wang. An improved multivariate polynomial factoring algorithm. Math. Comp., 32(144):1215--1231, 1978.
• 30: P. S. Wang and L. P. Rothschild. Factoring multivariate polynomials over the integers. Math. Comp., 29:935--950, 1975.
• 31: D. Y. Y. Yun. Uniform bounds for a class of algebraic mappings. SIAM J. on Computing, 8:348--356, 1979.
• 32: H. Zassenhaus. On Hensel factorization I. J. Number Theory, 1(1):291--311, 1969.
• 33: H. Zassenhaus. A remark on the Hensel factorization method. Math. Comp., 32(141):287--292, 1978.
• 34: R. Zippel. Effective Polynomial Computation. Kluwer Academic Publishers, 1993.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Theory

Keywords:
Hensel lifting, computer algebra, multi-moduli, polynomial factorization, tellegen, transposition principle