A modular GCD algorithm over number fields presented with multiple extensions

ABSTRACT

We consider the problem of computing the monic gcd of two polynomials over a number field L = ℚ(α1,…,αn). Encarnacion, Langemyr and McCallum have already shown how Brown's modular GCD algorithm for polynomials over ℚ can be modified to work for ℚ(α).Our first contribution is an extension of Encarnacion's modular GCD algorithm to the case n > 1 without converting to a single field extension. Our second contribution is a proof that it is not necessary to test if p divides the discriminant. This simplifies the algorithm; it is correct without this test.Our third contribution is the design of a data structure for representing multivariate polynomials over number fields with multiple field extensions. We have a complete implementation of the modular GCD algorithm using it. We provide details of some practical improvements.

REFERENCES

• 1: J. A. Abbott , R. J. Bradford , J. H. Davenport, The Bath algebraic number package, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.250-253, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32490]
• 2: R. Bradford, Some results on the defect, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.129-135, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74557]
• 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: Mark J. Encarnación, Computing GCDs of polynomials over algebraic number fields, Journal of Symbolic Computation, v.20 n.3, p.299-313, Sept. 1995 [doi>10.1006/jsco.1995.1052]
• 5: E. Hecke, Lectures on the Theory of Algebraic Numbers, Springer Graduate Texts in Mathematics77, (1981).
• 6: M. van Hoeij, M. Monagan, A Modular GCD algorithm over Number Fields presented with Multiple Extensions, FSU preprint 02-03, (2002).
• 7: Lars Langemyr , Scott McCallum, The computation of polynomial greatest common divisors over an algebraic number field, Journal of Symbolic Computation, v.8 n.5, p.429-448, Nov. 1989 [doi>10.1016/S0747-7171(89)80053-7]
• 8: Michael B. Monagan , Allan D. Wittkopf, On the design and implementation of Brown's algorithm over the integers and number fields, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.225-233, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345639]
• 9: D. Stoutemyer, Which Polynomial Representation is Best?, Proceedings of the 1984 Macsyma User's Conference, 1984.
• 10: Paul S. Wang , M. J. T. Guy , J. H. Davenport, P-adic reconstruction of rational numbers, ACM SIGSAM Bulletin, v.16 n.2, p.2-3, May 1982 [doi>10.1145/1089292.1089293]
• 11: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

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
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Proof theory

General Terms:
Algorithms, Experimentation, Theory