Mathematics of Computation

Author(s): Joachim von zur Gathen; Jürgen Gerhard.
Journal: Math. Comp. 71 (2002), 1677-1698.
MSC (2000): Primary 68W30; Secondary 11T06, 12Y05
Posted: May 3, 2002
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

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.15em$ Nauk 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 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.

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

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: 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
Posted: May 3, 2002
Additional Notes: This work was partly supported by the DFG Sonderforschungsbereich 376 ``Massive Parallelität: Algorithmen, Entwurfsmethoden, Anwendungen''.
Copyright of article: Copyright 2002, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS