The EZ GCD algorithm

ABSTRACT

This paper presents a preliminary report on a new algorithm for computing the Greatest Common Divisor (GCD) of two multivariate polynomials over the integers. The algorithm is strongly influenced by the method used for factoring multivariate polynomials over the integers. It uses an extension of the Hensel lemma approach originally suggested by Zassenhaus for factoring univariate polynomials over the integers. We point out that the cost of the Modular GCD algorithm applied to sparse multivariate polynomials grows at least exponentially in the number of variables appearing in the GCD. This growth is largely independent of the number of terms in the GCD. The new algorithm, called the EZ (Extended Zassenhaus) GCD Algorithm, appears to have a computing bound which in most cases is a polynomial function of the number of terms in the original polynomials and the sum of the degrees of the variables in them. Especially difficult cases for the EZ GCD Algorithm are described. Applications of the algorithm to the computation of contents and square-free decompositions of polynomials are indicated.

REFERENCES

• 1: Berlekamp, E. R., "Factoring Polynomials over Finite Fields", Bell System Technical Journal, Vol. 46, 1967, MR #2314, pp. 1853-1859.
• 2: Bonneau, R., "The Fast Fourier Transform and Polynomial Multiplications", Department of Mathematics, M.I.T. (in preparation).
• 3: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 4: Brown, W. S., Hyde, J. P., and Tague, B. A., "The ALPAK System for Numerical Algebra on a Digital Computer - II", The Bell System Technical Journal, March, 1964, pp. 785-804.
• 5: W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
• 6: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 7: George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971 [doi>10.1145/321662.321666]
• 8: Fateman, R. J., "On the Computation of Powers of Polynomials", Department of Mathematics, M.I.T. (unpublished).
• 9: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 10: MACSYMA User's Manual, by Bogen, R., et al., Project MAC, M.I.T., Cambridge, Mass., 1973.
• 11: Joel Moses, Towards a general theory of special functions, Communications of the ACM, v.15 n.7, p.550-554, July 1972 [doi>10.1145/361454.361466]
• 12: David Rea Musser, Algorithms for polynomial factorization., 1971
• 13: Proc. of the Second Symposium on Symbolic and Algebraic Manipulation, Petrick, S. R., ed., ACM, March, 1971.
• 14: Van der Waerden, B. L., Modern Algebra, Vol. 1, Frederic Ungar Publishing Co., N.Y., 1953.
• 15: Wang, P. S., and Rothschild, L. P., "Factoring Multivariate Polynomials over the Integers", (submitted to Mathematics of Computation).
• 16: Yun, D. Y. Y., "The Hensel Lemma in GCD Calculations", Department of Mathematics, M.I.T., (in preparation).
• 17: Zassenhaus, H., "On Hensel Factorization I", Journal of Number Theory, Vol. 1, 1969, pp. 291-311.

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: Computation of transforms (e.g., fast Fourier transform)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

General Terms:
Algorithms, Theory