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 Free Access

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?)

  • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR 0413592
  • Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794
  • David G. Cantor, On arithmetical algorithms over finite fields, J. Combin. Theory Ser. A 50 (1989), no. 2, 285–300. MR 989199, DOI
  • K. Dowd, High Performance Computing, O’Reilly & Associates Inc., 1993.
  • 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.
  • 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
  • J. von zur Gathen and J. Gerhard, Arithmetic and factorization of polynomials over $F_2$, Proc. ISSAC ’96, ACM Press, 1996, pp. 1-9.
  • K. O. Geddes, S. R. Czapor, and G. Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Boston, MA, 1992. MR 1256483
  • J. Gerhard, Faktorisieren von Polynomen über $\textbf {F}_q$: ein Vergleich neuerer Verfahren, Master’s thesis, University of Erlangen-Nürnberg, 1994.
  • IBM, AIX Version 3.2 for RISC System/6000: Optimization and Tuning Guide for Fortran, C, and C++, IBM Manual, 1993.
  • 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.
  • A. Karatsuba and Y. Ofman, Multiplication of multidigit numbers on automata, Soviet Phys. Dokl. 7 (1963), 595–596.
  • 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
  • D. Reischert, Schnelle Multiplikation von Polynomen über $GF(2)$ und Anwendungen, Master’s thesis, University of Bonn, 1995.
  • D. Reischert, Multiplication by a Square is cheap over $F_2$, Preprint, 1996.
  • Victor Shoup, A new polynomial factorization algorithm and its implementation, J. Symbolic Comput. 20 (1995), no. 4, 363–397. MR 1384454, DOI
  • V. Strassen, The computational complexity of continued fractions, SIAM J. Comput. 12 (1983), no. 1, 1–27. MR 687799, DOI
  • 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.
  • 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 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