Fast computation of GCDs

ABSTRACT

An integer greatest common divisor (GCD) algorithm due to Schönhage is generalized to hold in all euclidean domains which possess a fast multiplication algorithm. It is shown that if two N precision elements can be multiplied in O(N loga N), then their GCD can be computed in O(N loga+1 N). As a consequence, a new faster algorithm for multivariate polynomial GCD's can be derived and with that new bounds for rational function manipulation.

REFERENCES

• 1: A. Schönhager, Schnelle Berechnung von Kettenbruchentwicklugen, Acta Informatica 1, 139-144 (1971).
• 2: D. Knuth, "Mathematical Analysis of Algorithms", Stanford Comp. Sci. Tech. Report, STAN-CS-71-206, March 1971.
• 3: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 4: 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]
• 5: R. Moenck and A. Borodin, "Fast Modular Transforms via Division", Proc. 13th Annual Symp. on Switching and Automata Theory, 1972.
• 6: G.E. Collins, Computing Time Analysis for Some Arithmetic and Algebraic Algorithms, Proc. of 68 Summer Institute on Symbolic Mathematical Computation.
• 7: A. Borodin and I. Munro, "Evaluation of Polynomials at Many Points", Information Processing Letters, Vol. 1, No. 2, July 1971.
• 8: Ellis Horowitz, Algorithms for rational function arithmetic operations, Proceedings of the fourth annual ACM symposium on Theory of computing, p.108-118, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804903]
• 9: E. Horowitz, "A Fast Method for Interpolation Using Preconditioning", IPL, Vol. 2, No. 3.
• 10: E. Horowitz and L. Heindel, "On Decreasing the Computing Time for Modular Algorithms", Proc. of 12th Symp. on Switching and Automata Theory, Oct. 1971.
• 11: V. Strassen, Die Berechnungs-komplexitat von elementarsymetrischen Funktionen und von Interpolations-koeffizienten, University of Zurich, Preprint.
• 12: A. Ostrowski, On Two Problems in Abstract Algebra Connected with Horner's Rule, Studies presented to R. von Mises, Academic Press, New York, 1954, 40-48.

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:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms