Remote Access Mathematics of Computation
Green Open Access

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
DOI: https://doi.org/10.1090/S0025-5718-02-01421-7
Published electronically: May 3, 2002
MathSciNet review: 1933050
Full-text PDF

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?)

  • 1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading MA, 1974. MR 54:1706
  • 2. A. Arwin, Über Kongruenzen von dem fünften und höheren Graden nach einem Primzahlmodulus, Ark. Mat. 14 (1918), no. 7, 1-46.
  • 3. M. Ben-Or, Probabilistic algorithms in finite fields, Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science, Nashville TN, 1981, pp. 394-398.
  • 4. E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Technical Journal 46 (1967), 1853-1859. MR 36:2314
  • 5. -, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), no. 11, 713-735. MR 43:1948
  • 6. -, Algebraic coding theory, Aegean Park Press, 1984. First edition McGraw Hill, New York, 1968. MR 38:6873
  • 7. Olaf Bonorden, Joachim von zur Gathen, Jürgen Gerhard, Olaf Müller, and Michael Nöcker, Factoring a binary polynomial of degree over one million, ACM SIGSAM Bull. 35 (1), 2001, 16-18.
  • 8. David G. Cantor, On arithmetical algorithms over finite fields, J. Combin. Theory Ser. A 50 (1989), 285-300. MR 90f:11100
  • 9. David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), 693-701. MR 92i:68068
  • 10. David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587-592. MR 82e:12020
  • 11. Philippe Flajolet, Xavier Gourdon, and Daniel Panario, Random polynomials and polynomial factorization, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming ICALP 1996, Paderborn, Germany (F. Meyer auf der Heide and B. Monien, eds.), Lecture Notes in Comput. Sci., no. 1099, Springer-Verlag, 1996, pp. 232-243. INRIA Rapport de Recherche No 3370, March 1998, 28 pages. MR 98e:68123
  • 12. Peter Fleischmann and Peter Roelse, Comparative implementations of Berlekamp's and Niederreiter's polynomial factorization algorithms, Finite Fields and Applications, Proceedings of the third international conference, Glasgow, UK, July 1995 (S. Cohen and H. Niederreiter, eds.), London Math. Soc. Lecture Notes Ser., no. 233, Cambridge University Press, 1996, pp. 73-83. MR 98a:12009
  • 13. É. Galois, Sur la théorie des nombres, Bulletin des sciences mathématiques Férussac 13 (1830), 428-435. See also Journal de Mathématiques Pures et Appliquées 11 (1846), 398-407, and Écrits et mémoires d'Évariste Galois (Robert Bourgne and J.-P. Azra, eds.), Gauthier-Villars, Paris, 1962, 112-128. MR 27:21
  • 14. Shuhong Gao and Joachim von zur Gathen, Berlekamp's and Niederreiter's polynomial factorization algorithms, Finite Fields: Theory, Applications and Algorithms (G. L. Mullen and P. J.-S. Shiue, eds.), Contemp. Math., no. 168, American Mathematical Society, 1994, pp. 101-115. MR 95f:11106
  • 15. Joachim von zur Gathen and Jürgen Gerhard, Arithmetic and factorization of polynomials over $\mathbb{Z}_2$, Tech. Report tr-rsfb-96-018, University of Paderborn, Germany, 1996, 43 pages.
  • 16. -, Modern computer algebra, Cambridge University Press, Cambridge, UK, 1999. MR 2000j:68205
  • 17. J. von zur Gathen, X. Gourdon, and D. Panario, Average cost of baby-step/giant-step polynomial factorization algorithms, in preparation, 2002.
  • 18. Joachim von zur Gathen and Daniel Panario, Factoring polynomials over finite fields: A survey, J. Symbolic Comput. 31 (2001), no. 1-2, 3-17.CMP 2001:07
  • 19. Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), 187-224. MR 94d:12011
  • 20. Carl Friedrich Gauß, Theoria residuorum biquadraticorum, commentatio secunda, Werke II, Königliche Gesellschaft der Wissenschaften, Göttingen, 1863, reprinted by Georg Olms Verlag, Hildesheim New York, 1973, pp. 93-150. MR 82e:01022
  • 21. E. Kaltofen, Polynomial factorization 1987-1991, Proceedings of LATIN '92, São Paulo, Brazil (I. Simon, ed.), Lecture Notes in Comput. Sci., no. 583, Springer-Verlag, 1992, pp. 294-313. MR 94f:68019
  • 22. E. Kaltofen and A. Lobo, Factoring high-degree polynomials by the black box Berlekamp algorithm, Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation ISSAC '94, Oxford, UK (J. von zur Gathen and M. Giesbrecht, eds.), ACM Press, 1994, pp. 90-98.
  • 23. Erich Kaltofen and Victor Shoup, Fast polynomial factorization over high algebraic extensions of finite fields, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC '97, Maui HI (Wolfgang W. Küchlin, ed.), ACM Press, 1997, pp. 184-188. MR 2000i:68174
  • 24. -, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179-1197, Extended Abstract in Proceedings of the Twenty-seventh Annual ACM Symposium on the Theory of Computing, Las Vegas NV, ACM Press, 1995, 398-406. MR 99m:68097
  • 25. A. Karatsuba and Yu. Ofman, Umnozhenie mnogoznachnykh chisel na avtomatakh, Doklady Akademi{\u{\i}}\kern.15emNauk SSSR 145 (1962), 293-294. A. Karatsuba and Yu. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics-Doklady 7 (1963), 595-596.
  • 26. Arnold Knopfmacher and John Knopfmacher, Counting irreducible factors of polynomials over a finite field, Discrete Math. 112 (1993), 103-118. MR 94a:11188
  • 27. Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia Math. Appl., no. 20, Addison-Wesley, Reading MA, 1983. MR 86c:11106
  • 28. Peter L. Montgomery, Factorization of $X^{216091}+X+1\bmod 2$--A problem of Herb Doughty, manuscript, February 1991.
  • 29. Harald Niederreiter, New deterministic factorization algorithms for polynomials over finite fields, Finite fields: theory, applications and algorithms (G. L. Mullen and P. J.-S. Shiue, eds.), Contemp. Math., no. 168, American Mathematical Society, 1994, pp. 251-268. MR 95f:11100
  • 30. Daniel Reischert, Schnelle Multiplikation von Polynomen über GF(2) und Anwendungen, Diplomarbeit, Institut für Informatik II, Rheinische Friedrich-Wilhelm-Universität Bonn, Germany, August 1995.
  • 31. -, Multiplication by a square is cheap over $\mathbb{F}_2$, manuscript, 1996.
  • 32. Peter Roelse, Factoring high-degree polynomials over F$_2$ with Niederreiter's algorithm on the IBM SP2, Math. Comp. 68 (1999), no. 226, 869-880. MR 99i:11112
  • 33. A. Schönhage, Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Inform. 7 (1977), 395-398. MR 55:9604
  • 34. A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292. MR 45:1431
  • 35. J.-A. Serret, Cours d'algèbre supérieure, 3rd ed., Gauthier-Villars, Paris, 1866.
  • 36. Victor Shoup, A new polynomial factorization algorithm and its implementation, J. Symbolic Comput. 20 (1995), 363-397. MR 97d:12011
  • 37. V. Strassen, The computational complexity of continued fractions, SIAM J. Comput. 12 (1983), no. 1, 1-27. MR 84b:12004
  • 38. David Y. Y. Yun, On square-free decomposition algorithms, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation SYMSAC '76, Yorktown Heights NY (R. D. Jenks, ed.), ACM Press, 1976, pp. 26-35.

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: https://doi.org/10.1090/S0025-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

American Mathematical Society