Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Factoring high-degree polynomials over $\mathbf F_2$ with Niederreiter’s algorithm on the IBM SP2
HTML articles powered by AMS MathViewer

by Peter Roelse PDF
Math. Comp. 68 (1999), 869-880 Request permission

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
  • 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
  • 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 10.1016/0097-3165(89)90020-4
  • 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 10.1017/CBO9780511525988.009
  • 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, DOI 10.1007/b102438
  • 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 10.1090/conm/168/01705
  • 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 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
  • 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
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
  • Email: roelse@exp-math.uni-essen.de, roelse@crypto.philips.com
  • Received by editor(s): May 19, 1997
  • Received by editor(s) in revised form: August 11, 1997
  • © Copyright 1999 American Mathematical Society
  • Journal: Math. Comp. 68 (1999), 869-880
  • MSC (1991): Primary 11--04, 11T06, 11Y16
  • DOI: https://doi.org/10.1090/S0025-5718-99-01008-X
  • MathSciNet review: 1604383