Factoring a binary polynomial of degree over one million

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Factoring a binary polynomial of degree over one million

Full text

Pdf (217 KB)

Source

ACM SIGSAM Bulletin archive
Volume 35 , Issue 1 (March 2001) table of contents

Pages: 16 - 18

Year of Publication: 2001

ISSN:0163-5824

Authors

Olaf Bonorden	Univ. Paderborn, Paderborn, Germany
Joachim von zur Gathen	Univ. Paderborn, Paderborn, Germany
Jürgen Gerhard	Univ. Paderborn, Paderborn, Germany
Olaf Müller	Univ. Paderborn, Paderborn, Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 9, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/504331.504333 What is a DOI?

ABSTRACT

On 22 May 2000, the factorization of a pseudorandom polynomial of degree 1 048 543 over the binary field Z₂ was completed on a 4-processor Linux PC, using roughly 100 CPU-hours. The basic approach is a combination of the factorization software BIPOLAR and a parallel version of Cantor's multiplication algorithm. The PUB-library (Paderborn University BSP library) is used for the implementation of the parallel communication.

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	Olaf Bonorden, Nicolas Hüppelshäuser, Ben Juurlink & Ingo Rieping (1999). PUB-Library: User guide and function reference. Heinz Nixdorf Institute and Department of Computer Science, Univ. of Paderborn. Release 7.0 edition. URL http://www.upd.de/~pub/.
	2	David G. Gantor, On arithmetical algorithms over finite fields, Journal of Combinatorial Theory Series A, v.50 n.2, p.285-300, March 1989 [doi>10.1016/0097-3165(89)90020-4]
	3	David G. Cantor & Hans Zassenhaus (1981). A new algorithm for factoring polynomials over finite fields. Math. Comp. 36(154), 587-592.
	4	Joachim von zur Gathen , Jürgen Gerhard, Arithmetic and factorization of polynomial over F2 (extended abstract), Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.1-9, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236882]
	5	Joachim Von Zur Gathen , Daniel Panario, Factoring polynomials over finite fields: a survey, Journal of Symbolic Computation, v.31 n.1-2, p.3-17, Jan./Feb. 2001 [doi>10.1006/jsco.1999.1002]
	6	Joachim von zur Gathen & Victor Shoup (1992). Computing Frobenius maps and factoring polynomials. Computational Complexity 2, 187-224.
	7	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	8	Paul S. Wang, Parallel polynomial operations on SMPs: an overview, Journal of Symbolic Computation, v.21 n.4-6, p.397-410, April/May/June 1996 [doi>10.1006/jsco.1996.0021]

CITED BY 4

	Joachim von zur Gathen , Jürgen Gerhard, Polynomial factorization over F2, Mathematics of Computation, v.71 n.240, p.1677-1698, October 2002
	Erich Kaltofen, Polynomial factorization: a success story, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.3-4, August 03-06, 2003, Philadelphia, PA, USA
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Fatima K. Abu Salem, A new sparse Gaussian elimination algorithm and the Niederreiter linear system for trinomials over F2, Computing, v.77 n.2, p.179-203, April 2006