A modular greatest common divisor algorithm for gaussian polynomials

ABSTRACT

In this paper the Brown-Collins modular greatest common divisor algorithm for polynomials in Z[x1,...,xv], where Z denotes the ring of rational integers, is generalized to apply to polynomials in G[x1,...,xv], where G denotes the ring of Gaussian integers, i.e., complex numbers of the form a + ib where a, b are in Z Under certain simplifying assumptions, a function is found that dominates the maximum computing time of the new god algorithm.

REFERENCES

• 1: 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]
• 2: B. F. Caviness, G. E. Collins, H.I. Epstein, M. Rothstein, and S. C. Schaller, The SAC-1 Gaussian Integer and Gaussian Polynomial System, University of Wisconsin Computer Sciences Dept. Tech. Report (In preparation).
• 3: B. F. Caviness and G. E. Collins, Algorithms for Gaussian integer arithmetic (In preparation).
• 4: G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, London, 1960.

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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Gaussian quadrature

General Terms:
Algorithms, Theory