Mathematics of Computation

Factoring high-degree polynomials over ${\mathbf F}_2$ with Niederreiter's algorithm on the IBM SP2

Author(s): Peter Roelse.
Journal: Math. Comp. 68 (1999), 869-880.
MSC (1991): Primary 11--04, 11T06, 11Y16.
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: A

implementation of Niederreiter's algorithm for factoring polynomials over ${\mathbf F}_2$ is described. The most time-consuming part of this algorithm, which consists of setting up and solving a certain system of linear equations, is performed in parallel. Once a basis for the solution space is found, all irreducible factors of the polynomial can be extracted by suitable $\gcd$ -computations. For this purpose, asymptotically fast polynomial arithmetic algorithms are implemented. These include Karatsuba & Ofman multiplication, Cantor multiplication and Newton inversion. In addition, a new efficient version of the half-gcd algorithm is presented. Sequential run times for the polynomial arithmetic and parallel run times for the factorization are given. A new ``world record'' for polynomial factorization over the binary field is set by showing that a pseudo-randomly selected polynomial of degree 300000 can be factored in about 10 hours on 256 nodes of the IBM SP2 at the Cornell Theory Center.

1.: A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. MR 54:1706
2.: E. Bach and J. Shallit, Algorithmic Number Theory - Volume 1: Efficient Algorithms, The MIT Press, 1996. MR 97e:11157
3.: D.G. Cantor, On arithmetical algorithms over finite fields, J. Combin. Theory Ser. A 50, (1989), 285-300. MR 90f:11100
4.: K. Dowd, High Performance Computing, O'Reilly & Associates Inc., 1993.
5.: A. Diaz, E. Kaltofen and V. Pan, Algebraic algorithms, The Computer Science and Engineering Handbook (A.B. Tucker, ed.), CRC Press, 1997, pp. 226-249.
6.: P. Fleischmann and P. Roelse, Comparative implementations of Berlekamp's and Niederreiter's polynomial factorization algorithms, Finite Fields and their Applications (S. Cohen and H. Niederreiter, eds.), Cambridge University Press, 1996, pp. 73-84. MR 98a:12009
7.: J. von zur Gathen and J. Gerhard, Arithmetic and factorization of polynomials over , Proc. ISSAC '96, ACM Press, 1996, pp. 1-9.
8.: K.O. Geddes, S.R. Czapor and G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers, 1992. MR 96a:68049
9.: J. Gerhard, Faktorisieren von Polynomen über ${\bf F}_q$ : ein Vergleich neuerer Verfahren, Master's thesis, University of Erlangen-Nürnberg, 1994.
10.: IBM, AIX Version 3.2 for RISC System/6000: Optimization and Tuning Guide for Fortran, C, and C++, IBM Manual, 1993.
11.: E. Kaltofen and A. Lobo, Factoring high-degree polynomials by the black box Berlekamp algorithm, Proc. ISSAC '94 (J. von zur Gathen and M. Giesbrecht, eds.), ACM Press, 1994, pp. 90-98.
12.: A. Karatsuba and Y. Ofman, Multiplication of multidigit numbers on automata, Soviet Phys. Dokl. 7 (1963), 595-596.
13.: H. Niederreiter, New deterministic factorization algorithms for polynomials over finite fields, Contemp. Math. 168 (1994), 251-268. MR 95f:11100
14.: D. Reischert, Schnelle Multiplikation von Polynomen über und Anwendungen, Master's thesis, University of Bonn, 1995.
15.: D. Reischert, Multiplication by a Square is cheap over , Preprint, 1996.
16.: V. Shoup, A new polynomial factorization algorithm and its implementation, J. Symbolic Comput. 20 (1995), 363-397. MR 97d:12011
17.: V. Strassen, The computational complexity of continued fractions, SIAM J. Comput. 12 (1983), 1-27. MR 84b:12004
18.: M. Weller, Parallel Gaussian elimination over small finite fields, Parallel and Distributed Computing Systems, Proc. of the ISCA International Conference (K. Yetongnon and S. Hariri, eds.), 1996, 56-63.
19.: D.Y.Y. Yun, On square-free decomposition algorithms, Proc. ACM Symp. Symbolic and Algebraic Comput. (R.D. Jenks, ed.), 1976, pp. 26-35.

Retrieve articles in Mathematics of Computation with MSC (1991): 11--04, 11T06, 11Y16.

			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