On a modular algorithm for computing GCDs of polynomials over algebraic number fields

ABSTRACT

Modular methods for computing the gcd of two univariate polynomials over an algebraic number field require a priori knowledge about the denominators of the rational numbers in the representation of the gcd. We derive a multiplicative bound for these denominators without assuming that the number generating the field is an algebraic integer. Consequently, the gcd algorithm of Langemyr and McCallum [J. Symbolic Computation, 8:429-448, 1989] can now be applied directly to polynomials that are not necessarily represented in terms of an algebraic integer. Worst-case analyses and experiments with an implementation show that by avoiding a conversion of representation the reduction in the computing time can be significant. We also suggest the use of an algorithm for recovering a rational number from its modular residue so that the denominator bound need not be computed explicitly. Experiments and analyses indicate that this is a good practical alternative.

REFERENCES

• 1: Russell John Bradford, On the computation of integral bases and defects of integrity, 1988
• 2: Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 3: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 4: George E. Collins , Hoon Hong, Partial cylindrical algebraic decomposition for quantifier elimination, Journal of Symbolic Computation, v.12 n.3, p.299-328, Sept. 1991 [doi>10.1016/S0747-7171(08)80152-6]
• 5: M. J. Encarnaci6n. A Lehmer-type algorithm for recovering a rational number from its modular residue. In preparation, 1994.
• 6: E. Hecke. Lectures on the Theory of Algebraic Numbers. Graduate Texts in Mathematics. Springer-Verlag, 1981.
• 7: W. V. D. Hodge and D. Pedoe. Methods of Algebraic Geometry, Book I. Cambridge Uniw~rsity Press, 1946.
• 8: Hoon Hong , George E. Collins, Improvements in cad-based quantifier elimination, 1990
• 9: L. Langemyr. Computing She G CD of Swo Polynomials Over an Algebraic Number Field. PhD thesis, NADA, Royal Institute of Technology, Stockholm, Sweden, 1988.
• 10: Lars Langemyr, An Asymptotically Fast Probabilitstic Algorithm for Computing Polynominal GCD's over an Algebraic Number Field, Proceedings of the 8th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.222-233, August 20-24, 1990
• 11: 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]
• 12: Arjen K. Lenstra, Factoring polynominals over algebraic number fields, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.245-254, March 28-30, 1983
• 13: A. K. Lenstra. Polynomial-time Algorithms .for ~he Factorization of Polynomials. PhD thesis, Universiteit van Amsterdam, 1984.
• 14: R. Loos. Generalized polynomial remainder sequences. In B. Buchberger, G. E. Collins, and R. Loos, editors, Computer Algebra--Symbolic and Algebraic CompuSation, pages 115-138. Springer-Verlag, 2nd edition, 1982.
• 15: D. A. Marcus. Number Fields. Springer-Verlag, 1977.
• 16: M. Mignotte. An inequality about factors of polynomials. Mathematics of Computation, 28(128):1153-1157, 1974.
• 17: M. Mignotte. Some useful bounds. In B. Buchberger, G. E. Collins, and R. Loos, editors, Computer Algebra~Symbolic and Algebraic Computation, pages 259-263. Springer-Verlag, 2nd edition, 1982.
• 18: Bhubaneswar Mishra, Algorithmic algebra, Springer-Verlag New York, Inc., New York, NY, 1993
• 19: M. E. Pohst. Computational Algebraic Number Theory. DMV Seminar Band 21. Springer-Verlag, 1993.
• 20: Cyrenus Matthew Rubald, Algorithms for polynomials over a real algebraic number field., 1973
• 21: SACLIB 1.1 User's Guide. Technical Report 93-19, RISC-Linz, Johannes Kepler University, A-4040 Linz, Austria, March 1993.
• 22: T. J. Smedley, A new modular algorithm for computation of algebraic number polynomial gcds, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.91-94, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74552]
• 23: Paul S. Wang, A p-adic algorithm for univariate partial fractions, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.212-217, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806398]
• 24: 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]
• 25: P. J. Weinberger , L. P. Rothschild, Factoring Polynomials Over Algebraic Number Fields, ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.335-350, Dec. 1976 [doi>10.1145/355705.355709]

INDEX TERMS

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

Additional 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); Computations on polynomials

General Terms:
Algorithms, Experimentation, Theory, Verification