Polynomial factorization over ${\mathbb F}_2$
HTML articles powered by AMS MathViewer
- by Joachim von zur Gathen and Jürgen Gerhard PDF
- Math. Comp. 71 (2002), 1677-1698 Request permission
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
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
- A. Arwin, Über Kongruenzen von dem fünften und höheren Graden nach einem Primzahlmodulus, Ark. Mat. 14 (1918), no. 7, 1–46.
- 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.
- E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.1538-7305.1967.tb03174.x
- E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X
- Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
- 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.
- David G. Cantor, On arithmetical algorithms over finite fields, J. Combin. Theory Ser. A 50 (1989), no. 2, 285–300. MR 989199, DOI 10.1016/0097-3165(89)90020-4
- David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693–701. MR 1129288, DOI 10.1007/BF01178683
- David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592. MR 606517, DOI 10.1090/S0025-5718-1981-0606517-5
- Philippe Flajolet, Xavier Gourdon, and Daniel Panario, Random polynomials and polynomial factorization, Automata, languages and programming (Paderborn, 1996) Lecture Notes in Comput. Sci., vol. 1099, Springer, Berlin, 1996, pp. 232–243. MR 1464452, DOI 10.1007/3-540-61440-0_{1}31
- Peter Fleischmann and Peter Roelse, Comparative implementations of Berlekamp’s and Niederreiter’s polynomial factorization algorithms, Finite fields and applications (Glasgow, 1995) London Math. Soc. Lecture Note Ser., vol. 233, Cambridge Univ. Press, Cambridge, 1996, pp. 73–83. MR 1433141, DOI 10.1017/CBO9780511525988.009
- Robert Bourgne and J.-P. Azra, Ecrits et mémoires mathématiques d’Évariste Galois: Édition critique intégrale de ses manuscrits et publications, Gauthier-Villars & Cie, Éditeur-Imprimeur-Libraire, Paris, 1962 (French). Préface de J. Dieudonné. MR 0150016
- Shuhong Gao and Joachim von zur Gathen, Berlekamp’s and Niederreiter’s polynomial factorization algorithms, Finite fields: theory, applications, and algorithms (Las Vegas, NV, 1993) Contemp. Math., vol. 168, Amer. Math. Soc., Providence, RI, 1994, pp. 101–116. MR 1291420, DOI 10.1090/conm/168/01691
- 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.
- Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
- Joachim von zur Gathen, X. Gourdon, and D. Panario, Average cost of baby-step/giant-step polynomial factorization algorithms, in preparation, 2002.
- Joachim von zur Gathen and Daniel Panario, Factoring polynomials over finite fields: A survey, J. Symbolic Comput. 31 (2001), no. 1–2, 3–17.
- Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
- M. L. Sharma, Āryabhaṭa’s contribution to Indian astronomy, Proceedings of the Symposium on the 1500th Birth Anniversary of Āryabhaṭa I (New Delhi, 1976), 1977, pp. 90–99. MR 564823
- I. Simon (ed.), LATIN ’92, Lecture Notes in Computer Science, vol. 583, Springer-Verlag, Berlin, 1992. MR 1253341, DOI 10.1007/BFb0023811
- 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.
- Yu Ping Zhang, Deduction properties of some logics applied to computer science, Chinese J. Comput. 22 (1999), no. 6, 571–576 (Chinese, with English and Chinese summaries). MR 1731947
- Erich Kaltofen and Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179–1197. MR 1459389, DOI 10.1090/S0025-5718-98-00944-2
- A. Karatsuba and Yu. Ofman, Umnozhenie mnogoznachnykh chisel na avtomatakh, Doklady Akademiĭ Nauk SSSR 145 (1962), 293–294. A. Karatsuba and Yu. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics–Doklady 7 (1963), 595–596.
- Arnold Knopfmacher and John Knopfmacher, Counting irreducible factors of polynomials over a finite field, Discrete Math. 112 (1993), no. 1-3, 103–118. MR 1213754, DOI 10.1016/0012-365X(93)90227-K
- Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
- Peter L. Montgomery, Factorization of $X^{216091}+X+1\bmod 2$—A problem of Herb Doughty, manuscript, February 1991.
- Harald Niederreiter, New deterministic factorization algorithms for polynomials over finite fields, Finite fields: theory, applications, and algorithms (Las Vegas, NV, 1993) Contemp. Math., vol. 168, Amer. Math. Soc., Providence, RI, 1994, pp. 251–268. MR 1291434, DOI 10.1090/conm/168/01705
- 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.
- —, Multiplication by a square is cheap over $\mathbb {F}_2$, manuscript, 1996.
- Peter Roelse, Factoring high-degree polynomials over $\textbf {F}_2$ with Niederreiter’s algorithm on the IBM SP2, Math. Comp. 68 (1999), no. 226, 869–880. MR 1604383, DOI 10.1090/S0025-5718-99-01008-X
- A. Schönhage, Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Informat. 7 (1976/77), no. 4, 395–398. MR 0436663, DOI 10.1007/bf00289470
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
- J.-A. Serret, Cours d’algèbre supérieure, 3rd ed., Gauthier-Villars, Paris, 1866.
- Victor Shoup, A new polynomial factorization algorithm and its implementation, J. Symbolic Comput. 20 (1995), no. 4, 363–397. MR 1384454, DOI 10.1006/jsco.1995.1055
- V. Strassen, The computational complexity of continued fractions, SIAM J. Comput. 12 (1983), no. 1, 1–27. MR 687799, DOI 10.1137/0212001
- 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.
Additional Information
- Joachim von zur Gathen
- Affiliation: Fachbereich 17 Mathematik-Informatik, Universität Paderborn, D-33095 Paderborn, Germany
- MR Author ID: 71800
- Email: gathen@upb.de
- Jürgen Gerhard
- Affiliation: Fachbereich 17 Mathematik-Informatik, Universität Paderborn, D-33095 Paderborn, Germany
- Email: jngerhar@upb.de
- 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”.
- © Copyright 2002 American Mathematical Society
- 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
- MathSciNet review: 1933050