Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2024 MCQ for Mathematics of Computation is 1.78.

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.

 

The black-box Niederreiter algorithm and its implementation over the binary field
HTML articles powered by AMS MathViewer

by Peter Fleischmann, Markus Chr. Holder and Peter Roelse;
Math. Comp. 72 (2003), 1887-1899
DOI: https://doi.org/10.1090/S0025-5718-03-01494-7
Published electronically: April 21, 2003

Abstract:

The most time-consuming part of the Niederreiter algorithm for factoring univariate polynomials over finite fields is the computation of elements of the nullspace of a certain matrix. This paper describes the so-called “black-box” Niederreiter algorithm, in which these elements are found by using a method developed by Wiedemann. The main advantages over an approach based on Gaussian elimination are that the matrix does not have to be stored in memory and that the computational complexity of this approach is lower. The black-box Niederreiter algorithm for factoring polynomials over the binary field was implemented in the C programming language, and benchmarks for factoring high-degree polynomials over this field are presented. These benchmarks include timings for both a sequential implementation and a parallel implementation running on a small cluster of workstations. In addition, the Wan algorithm, which was recently introduced, is described, and connections between (implementation aspects of) Wan’s and Niederreiter’s algorithm are given.
References
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2000): 11-04, 11T06, 11Y16
  • Retrieve articles in all journals with MSC (2000): 11-04, 11T06, 11Y16
Bibliographic Information
  • Peter Fleischmann
  • Affiliation: Institute of Mathematics and Statistics, University of Kent, Canterbury, CT2 7NF, England
  • Email: p.fleischmann@ukc.ac.uk
  • Markus Chr. Holder
  • Affiliation: Westdeutsche Landesbank, Düsseldorf/Münster, Germany
  • Email: markus.holder@epost.de
  • Peter Roelse
  • Affiliation: Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
  • Address at time of publication: Philips Semiconductors, B.V., P.O. Box 218, 5600 MD Eindhoven, The Netherlands
  • Email: peter.roelse@philips.com
  • Received by editor(s): July 23, 2001
  • Received by editor(s) in revised form: February 7, 2002
  • Published electronically: April 21, 2003
  • © Copyright 2003 American Mathematical Society
  • Journal: Math. Comp. 72 (2003), 1887-1899
  • MSC (2000): Primary 11-04, 11T06, 11Y16
  • DOI: https://doi.org/10.1090/S0025-5718-03-01494-7
  • MathSciNet review: 1986810