Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



The black-box Niederreiter algorithm and its implementation over the binary field

Authors: Peter Fleischmann, Markus Chr. Holder and Peter Roelse
Journal: Math. Comp. 72 (2003), 1887-1899
MSC (2000): Primary 11-04, 11T06, 11Y16
Published electronically: April 21, 2003
MathSciNet review: 1986810
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

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

Additional Information

Peter Fleischmann
Affiliation: Institute of Mathematics and Statistics, University of Kent, Canterbury, CT2 7NF, England

Markus Chr. Holder
Affiliation: Westdeutsche Landesbank, Düsseldorf/Münster, Germany

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

Keywords: Finite fields, polynomial factorization, implicit linear algebra
Received by editor(s): July 23, 2001
Received by editor(s) in revised form: February 7, 2002
Published electronically: April 21, 2003
Article copyright: © Copyright 2003 American Mathematical Society