Polynomial factorization over 𝔽₂

von zur Gathen, Joachim; Gerhard, Jürgen

doi:10.1090/S0025-5718-02-01421-7

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.