Algorithms for polynomial GCD computation over algebraic function fields

ABSTRACT

Let L be an algebraic function field in k ≥ 0 parameters t;_1;, ..., t;_k;. Let f;_1;, f;_2; be non-zero polynomials in L[x]. We give two algorithms for computing their gcd. The first, a modular GCD algorithm, is an extension of the modular GCD algorithm of Brown for Z[x;_1;,...,x;_n;] and Encarnacion for Q(α)[x] to function fields. It is uses rational number and rational function reconstruction and trial division. The second, a fraction-free algorithm, is a modification of the Moreno Maza and Rioboo algorithm for computing gcds over triangular sets. The modification reduces coefficient growth in L to be linear. We show how to extend the modular GCD algorithm to work when the minimal polynomial for L is not irreducible. We give an empirical comparison of the two algorithms using implementations in Maple.

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: J. J. Cannon (2003). Magma Handbook, http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm
• 5: George E. Collins , Mark J. Encarnación, Efficient rational number reconstruction, Journal of Symbolic Computation, v.20 n.3, p.287-297, Sept. 1995 [doi>10.1006/jsco.1995.1051]
• 6: 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]
• 7: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 8: The GNU Multiple Precision Arithmetic Library. Copyright, Free Software Foundation, Inc. (2002). http://www.gnu.org/software/gmp/gmp.html
• 9: E. Hecke (1981). Lectures on the Theory of Algebraic Numbers, Springer Graduate Texts in Mathematics 77.
• 10: Mark van Hoeij , Michael Monagan, A modular GCD algorithm over number fields presented with multiple extensions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.109-116, July 07-10, 2002, Lille, France [doi>10.1145/780506.780520]
• 11: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 12: 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]
• 13: 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
• 14: D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, v.13 n.2, p.117-131, Feb. 1992 [doi>10.1016/S0747-7171(08)80086-7]
• 15: Michael Kalkbrener, A generalized Euclidean algorithm for computing triangular representations of algebraic varieties, Journal of Symbolic Computation, v.15 n.2, p.143-167, Feb. 1993 [doi>10.1006/jsco.1993.1011]
• 16: Marc Moreno Maza , Renaud Rioboo, Polynomial Gcd Computations over Towers of Algebraic Extensions, Proceedings of the 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.365-382, July 17-22, 1995
• 17: Maple 8 Introductory Programming Guide M. B. Monagan, K. O. Geddes, K. M. Heal, G. Labahn, S. M. Vorkoetter, J. McCarron, P. DeMarco. Waterloo Maple, 2002. ISBN: 1-894511-27-1.
• 18: Michael B. Monagan, In-place Arithmetic for Polinominals over Zn, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.22-34, April 13-15, 1992
• 19: 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]
• 20: Peter Lawrence Montgomery, An FFT extension of the elliptic curve method of factorization, University of California at Los Angeles, Los Angeles, CA, 1992
• 21: Victor Y. Pan , Xinmao Wang, Acceleration of Euclidean algorithm and extensions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.207-213, July 07-10, 2002, Lille, France [doi>10.1145/780506.780533]
• 22: A. Steel (2003). Private communication.
• 23: D. Stoutemyer (1984). Which Polynomial Representation is Best? Proceedings of the 1984 Macsyma User's Conference.
• 24: Barry M. Trager, Algebraic factoring and rational function integration, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.219-226, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806338]
• 25: 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]
• 26: 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]
• 27: 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: Algebraic algorithms

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms

Keywords:
modular algorithms