Factorization in Z[x]: the searching phase

ABSTRACT

In this paper we describe ideas used to accelerate the Searching Phase of the Berlekamp—Zassenhaus algorithm, the algorithm most widely used for computing factorizations in Z[x]. Our ideas do not alter the theoretical worst-case complexity, but they do have a significant effect in practice: especially in those cases where the cost of the Searching Phase completely dominates the rest of the algorithm. A complete implementation of the ideas in this paper is publicly available in the library NTL [16]. We give timings of this implementation on some difficult factorization problems.

REFERENCES

• 1: J. A. Abbott , R. J. Bradford , J. H. Davenport, A remark on factorisation, ACM SIGSAM Bulletin, v.19 n.2, p.31-33, May 1985 [doi>10.1145/1089402.1089408]
• 2: Berlekamp, E. R. Factoring polynomials over large finite fields. Mathematics of Computation 2~, 111 (1970), 713-735.
• 3: George E. Collins , Mark J. Encarnación, Improved techniques for factoring univariate polynomials, Journal of Symbolic Computation, v.21 n.3, p.313-327, March 1996 [doi>10.1006/jsco.1996.0014]
• 4: George E. Collins, Factoring univariate integral polynomial in polynomial average time, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.317-329, June 01, 1979
• 5: Davenport, J., and Mignotte, M. On finding the largest root of a polynomial. Mod~lisation Math~matique et Analyse Num~rique 2~, 6 (1990), 693-696.
• 6: Faug~re, J.-C. How my computer found all the solutions of Cyclic 9. Tech. Rep. 007, Rapport LIP6, 2000.
• 7: Kaltofen, E. Polynomial factorization. In Computer Algebra, B. Buchberger et alii, Ed., 2 ed. Springer Verlag, 1982, pp. 95-113.
• 8: Kaltofen, E. Polynomial factorization 1982-1986. In Computers in Mathematics, Chudnovsky and Jenks, Eds., vol. 125 of Lecture Notes in Pure and Applied Mathematics. Marcel Dekker, 1990, pp. 285-309.
• 9: Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
• 10: Kaltofen, E., Musser, D., and Saunders, B. D. A generalized class of polynomials that are hard to factor. SIAM J. Comput. 12, 3 (1983), 473-483.
• 11: Lenstra, A. K., Lenstra, H. W., and Lov~sz, L. Factoring polynomials with rational coefficients. Mathematische Annalen 261 (1982), 515-534.
• 12: Mignotte, M. An inequality about factors of polynomials. Mathematics of Computation 23, 128 (1974), 1153-1157.
• 13: 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]
• 14: Albert Nijenhuis , Herbert S. Will, Combinatorial Algorithms: For Computers and Hard Calculators, Academic Press, Inc., Orlando, FL, 1978
• 15: Rouillier, F. Solving zero-dimensional systems through the Rational Univariate Representation. Journal of Applicable Algebra in Engineering, Communication and Computing 9, 5 (1999), 433-461.
• 16: Shoup, V. NTL: A library for doing number theory. http: //www. shoup, net/nt 1/.
• 17: Paul S. Wang, Early detection of true factors in univariate polynominal factorization, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.225-235, March 28-30, 1983
• 18: Zassenhaus, H. On Hensel factorization I. Journal of Number Theory i (1969), 291-311.
• 19: Zimmermann, P. Polynomial factorization challenges: a collection of polynomials difficult to factor. ht tp: //www. 1 ori a. fr / ~ z immerma/mupad/.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Experimentation, Performance