Multivariate Polynomial Factorization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multivariate Polynomial Factorization

Full text

Pdf (1.35 MB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 2 (April 1975) table of contents

Pages: 291 - 308

Year of Publication: 1975

ISSN:0004-5411

Author

David R. Musser

Information Sciences Institute, University of Southern California, 4676 Admiralty Way, Marina del Rey, CA and University of Wisconsin, Madison, Wisconsin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 44, Citation Count: 17

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/321879.321890 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	BERLKAMP, E R Algebraic Coding Theory. McGraw-Hill, New York, 1968
	2	BERLEKAMP, E.R. Factoring polynomzals over large fimte fields Math. Comput 24, 111 (July 1970), 713-735
	3	CARLETON, R T A Pascal lmplementatmn of algorithms for the factorizatlon and greatest common diwsor calculatmn of multivariate polynommls. Master's Th , U. of Texas, Austin, Texas, Aug 1973
	4	George E. Collins, The SAC-1 system: An introduction and survey, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.144-152, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806279]
	5	COLLIns, G. E Computer algebra of polynommls and rational functions. Amer. Math Mon. 80, 7 (Aug -Sept 1973), 725-755
	6	COLLINS, GEORGE E , HEINDEL, L E , -IOROWITZ, E , McCLELLAN, M T , AND MUSSER, D R. The SAC-1 modular arithmetic system. Tech Rep. No. 10, U of Wisconsin, Madmon, Wlsc , June 1969.
	7	COLLINS, GEORGE E , AND MUSSER, D R. The SAC-1 polynomial factorizatlon system Comput. Sciences Teeh Rep No 157, U of Wisconsin, Madison, Wlsc , March 1972
	8	FLOYD, ROBERT W. Asslgmng meanings to programs Proc of a Symp m Apphed Mathematics, Vol. 19. Mathematical Aspects of Computer Science, J. T Schwartz, E d , Amer Math Soc , Providence, RI , 1967, pp 19-32
	9	GELFOND, A O. Transcendental and Algebraic Numbers Dover, New York, 1960.
	10	HOROWITZ, ELLIS Algorithms for symbohc integration of rational functions Ph D. Th, Comput Scmnces Dep , U of Wisconsin, Madmon, Wmc , 1969
	11	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	12	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	13	MIGNOTTE, M An inequality about factors of polynomials Math Comput (to appear)
	14	David Rea Musser, Algorithms for polynomial factorization., 1971
	15	RAnN, MICHAEL O Computable algebra, general theory and theory of computable fields Trans Amer Math Soc 95 (1960), 341-360
	16	VAN DER WAERDEN, B L Modern Algebra, Vol I (transl by Fred Blum). Ungar, New York, 1949
	17	Paul S. Wang , L. Preiss Rothschild, Factoring multivariate polynomials over the integers, ACM SIGSAM Bulletin [doi>10.1145/1086814.1086819]
	18	ZASSENHAS, HANS On Hensel factorlzatlon, I J Numer Theory 1 (1969), 291-311.

CITED BY 17

	E. Kaltofen, Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.443-452, January 1987, New York, New York, United States
	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
	Michael T. McClellan, The Exact Solution of Linear Equations with Rational Function Coefficients, ACM Transactions on Mathematical Software (TOMS), v.3 n.1, p.1-25, March 1977
	David Y. Y. Yun, Algebraic algorithms using p-adic constructions, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.248-259, August 10-12, 1976, Yorktown Heights, New York, United States
	David R. Musser, On the Efficiency of a Polynomial Irreducibility Test, Journal of the ACM (JACM), v.25 n.2, p.271-282, April 1978
	Laurent Bernardin , Bruce Char , Erich Kaltofen, Symbolic computation in Java: an appraisement, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.237-244, July 28-31, 1999, Vancouver, British Columbia, Canada
	Erich Kaltofen , David R. Musser , B. David Saunders, A generalized class of polynomials that are hard to factor, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.188-194, August 05-07, 1981, Snowbird, Utah, United States
	James R. Pinkert, An Exact Method for Finding the Roots of a Complex Polynomial, ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.351-363, Dec. 1976
	John Abbott , Victor Shoup , Paul Zimmermann, Factorization in Z[x]: the searching phase, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.1-7, July 2000, St. Andrews, Scotland
	Erich Kaltofen, A polynomial reduction from multivariate to bivariate integral polynomial factorization., Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.261-266, May 05-07, 1982, San Francisco, California, United States
	Richard Zippel, Newton's iteration and the sparse Hensel algorithm (Extended Abstract), Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.68-72, August 05-07, 1981, Snowbird, Utah, United States
	Yiu-Kwong Man , Francis J. Wright, Fast polynomial dispersion computation and its application to indefinite summation, Proceedings of the international symposium on Symbolic and algebraic computation, p.175-180, July 20-22, 1994, Oxford, United Kingdom
	Shuhong Gao , Alan G. B. Lauder, Hensel lifting and bivariate polynomial factorisation over finite fields, Mathematics of Computation, v.71 n.240, p.1663-1676, October 2002
	P. S. Wang, Parallel univariate polynomial factorization on shared-memory multiprocessors, Proceedings of the international symposium on Symbolic and algebraic computation, p.145-151, August 20-24, 1990, Tokyo, Japan
	Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003
	A. Bostan , G. Lecerf , B. Salvy , É. Schost , B. Wiebelt, Complexity issues in bivariate polynomial factorization, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.42-49, July 04-07, 2004, Santander, Spain
	Fatima K. Abu Salem, An efficient sparse adaptation of the polytope method over Fp and a record-high binary bivariate factorisation, Journal of Symbolic Computation, v.43 n.5, p.311-341, May, 2008