Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Polynomial factorization over ${\mathbb F}_2$


Authors: Joachim von zur Gathen and Jürgen Gerhard
Journal: Math. Comp. 71 (2002), 1677-1698
MSC (2000): Primary 68W30; Secondary 11T06, 12Y05
Published electronically: May 3, 2002
MathSciNet review: 1933050
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We describe algorithms for polynomial factorization over the binary field ${\mathbb F}_2$, and their implementation. They allow polynomials of degree up to $250\,000$ to be factored in about one day of CPU time, distributing the work on two processors.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 68W30, 11T06, 12Y05

Retrieve articles in all journals with MSC (2000): 68W30, 11T06, 12Y05


Additional Information

Joachim von zur Gathen
Affiliation: Fachbereich 17 Mathematik-Informatik, Universität Paderborn, D-33095 Paderborn, Germany
Email: gathen@upb.de

Jürgen Gerhard
Affiliation: Fachbereich 17 Mathematik-Informatik, Universität Paderborn, D-33095 Paderborn, Germany
Email: jngerhar@upb.de

DOI: http://dx.doi.org/10.1090/S0025-5718-02-01421-7
PII: S 0025-5718(02)01421-7
Keywords: Fast algorithms, finite fields, Frobenius automorphism, polynomial factorization
Received by editor(s): July 28, 2000
Published electronically: May 3, 2002
Additional Notes: This work was partly supported by the DFG Sonderforschungsbereich 376 “Massive Parallelität: Algorithmen, Entwurfsmethoden, Anwendungen”.
Article copyright: © Copyright 2002 American Mathematical Society