On the genericity of the modular polynomial GCD algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the genericity of the modular polynomial GCD algorithm

Full text

Pdf (885 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1999 international symposium on Symbolic and algebraic computation table of contents

Vancouver, British Columbia, Canada

Pages: 59 - 66

Year of Publication: 1999

ISBN:1-58113-073-2

Authors

Erich Kaltofen	North Carolina State University, Mathematics Department, Box 8205 Raleigh, N.C
Michael B. Monagan	Centre for Experimental and Constructive Mathematics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6 Canada

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 14, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/309831.309861 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Laurent Bernardin , Michael B. Monagan, Efficient Multivariate Factorization over Finite Fields, Proceedings of the 12th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.15-28, June 23-27, 1997
	2	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]
	3	B. F. Caviness , G. E. Collins, Algorithms for Gaussian integer arithmetic, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.36-45, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806321]
	4	B. F. Caviness , Michael Rothstein, A modular greatest common divisor algorithm for gaussian polynomials, Proceedings of the 1975 annual conference, p.270-273, January 1975 [doi>10.1145/800181.810340]
	5	Angel Díaz , Erich Kaltofen, On computing greatest common divisors with polynomials given by black boxes for their evaluations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.232-239, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220375]
	6	Angel Díaz , Erich Kaltofen, FOXBOX: a system for manipulating symbolic objects in black box representation, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.30-37, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281538]
	7	DOBBER'VIN, H. Ahnost perfect nonlinear power fu~mtions on GF(2"): The Niho case. Manuscript, German Inh)rmation Security Agency, Bonn, Germany, Apr. 1998.
	8	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]
	9	GAUSS, C. F. Disquisitioncs Arithmeticae. G. Fleis(:her, Jr., Leipzig, Germany, 1801.
	10	Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
	11	GOLDSTEIN. A. J.. ANI) Gt,~:XH.~XM, }}. L. A Hadamardtype bound on the coefficients of a determinant of polynomials. SIAM Rev. 16 (1974), 394-395.
	12	GRUNTZ. D.. AND ~;iONAGAN. h'i. B. Introduction to Gaus,~. No. 9 in Maple T(.~t:llni(:al Newsletter. Birkh~user, 1993, pp. 23-35.
	13	Erich Kaltofen, Sparse Hensel Lifting, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.4-17, April 01-03, 1985
	14	KALTOFEN. E. Spa.rse Hensel lifting. Tech. Rep. 85- 12, Rensselaer Polytechnic Instit., Dept. Comput. Sci., Troy, N. Y., 1985.
	15	Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988 [doi>10.1145/42267.45069]
	16	KALTOFV..N, E., ANt) ROLLETS(::HEK, H. Computing grea.test common divisors and factorizations in quadratic number fields. Math. Comput. 53, 188 (1989), 697-720.
	17	Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
	18	I(NU'VH. D. E. Seminumerical Algorithms, Third eel., vol. 2 of The Art of Computer Programming. Addison Wesley, Reading, Massachusetts, USA, 1997.
	19	Michael Monagan , Roger Margot, Computing univariate GCDs over number fields, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.42-49, January 25-27, 1998, San Francisco, California, United States
	20	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
	21	David Rea Musser, Algorithms for polynomial factorization., 1971

CITED BY 2

	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
	Howard Cheng , George Labahn, Output-sensitive modular algorithms for polynomial matrix normal forms, Journal of Symbolic Computation, v.42 n.7, p.733-750, July, 2007