Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Author: Peter Roelse
Journal: Math. Comp. 68 (1999), 869-880
MSC (1991): Primary 11--04, 11T06, 11Y16.
MathSciNet review: 1604383
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A $C$ 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.

References [Enhancements On Off] (What's this?)

  • 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 $F_2$, 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 $GF(2)$ und Anwendungen, Master's thesis, University of Bonn, 1995.
  • 15. D. Reischert, Multiplication by a Square is cheap over $F_2$, 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.

Similar Articles

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

Retrieve articles in all journals with MSC (1991): 11--04, 11T06, 11Y16.

Additional Information

Peter Roelse
Affiliation: Institute for Experimental Mathematics, University of Essen, Ellernstrasse 29, 45326 Essen, Germany
Address at time of publication: Philips Crypto B.V., De Witbogt 2, 5652 AG Eindhoven, The Netherlands

Keywords: Finite fields, parallel computing, polynomial factorization
Received by editor(s): May 19, 1997
Received by editor(s) in revised form: August 11, 1997
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society