Factoring polynomials via polytopes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Factoring polynomials via polytopes

Full text

Pdf (277 KB)

Source

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

Santander, Spain

Pages: 4 - 11

Year of Publication: 2004

ISBN:1-58113-827-X

Authors

Fatima Abu Salem	Oxford University, Oxford, UK
Shuhong Gao	Clemson University, Clemson, South Carolina
Alan G. B. Lauder	Oxford University, Oxford, UK

Sponsors

ACM: Association for Computing Machinery
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 22, Citation Count: 5

Additional Information:

abstract 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/1005285.1005289 What is a DOI?

ABSTRACT

We introduce a new approach to multivariate polynomial factorisation which incorporates ideas from polyhedral geometry, and generalises Hensel lifting. Our main contribution is to present an algorithm for factoring bivariate polynomials which is able to exploit to some extent the sparsity of polynomials. We give details of an implementation which we used to factor randomly chosen sparse and composite polynomials of high degree over the binary field.

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	F. Abu Salem, S. Gao, and A. G. B. Lauder "Factoring polynomials via polytopes: extended version", Report PRG-RR-04-07, Oxford University Computing Laboratory, 2004.
	2	S. Gao, "Absolute irreducibility of polynomials via Newton polytopes," J. of Algebra 237 (2001), 501--520.
	3	S. Gao and A.G.B. Lauder, "Decomposition of polytopes and polynomials", Discrete and Computational Geometry 26 (2001), 89--104.
	4	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 [doi>10.1090/S0025-5718-01-01393-X]
	5	S. Gao and A.G.B. Lauder, Fast absolute irreducibility testing via Newton polytopes, preprint 2003.
	6	Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
	7	Joachim von zur Gathen , Erich Kaltofen, Factoring sparse multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.265-287, Sept. 1985 [doi>10.1016/0022-0000(85)90044-3]
	8	R. L. Graham, "An efficient algorithm for determining the convex hull of a finite planar set", Inform. Process. Lett. 1 (1972), 132--3.
	9	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]
	10	D. Wan, "Factoring polynomials over large finite fields", Math. Comp. 54 (1990), No. 190, 755--770.

CITED BY 5

	Guillaume Chèze , Grégoire Lecerf, Lifting and recombination techniques for absolute factorization, Journal of Complexity, v.23 n.3, p.380-420, June, 2007
	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
	Fatima K. Abu Salem , Laurence T. Yang, Parallel methods for absolute irreducibility testing, The Journal of Supercomputing, v.46 n.3, p.181-212, December 2008
	Clément M. Gosselin , Brian Moore , Josef Schicho, Dynamic balancing of planar mechanisms using toric geometry, Journal of Symbolic Computation, v.44 n.9, p.1346-1358, September, 2009
	M. Elkadi , A. Galligo , M. Weimann, Towards toric absolute factorization, Journal of Symbolic Computation, v.44 n.9, p.1194-1211, September, 2009