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

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

  • 1. E.R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), pp. 1853-1859. MR 36:2314
  • 2. D.G. Cantor, On arithmetical algorithms over finite fields, J. Combin. Theory Ser. A 50, (1989), pp. 285-300. MR 90f:11100
  • 3. D.G. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), pp. 587-592. MR 82e:12020
  • 4. P. Fleischmann, Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields, Linear Algebra Appl. 192 (1993), pp. 101-108. MR 94f:11129
  • 5. 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
  • 6. S. Gao and J. von zur Gathen, Berlekamp's and Niederreiter's polynomial factorization algorithms, Contemp. Math. 168 (1994), pp. 101-116. MR 95f:11106
  • 7. M. Chr. Holder, Arithmetik grossgradiger Polynome über kleinen endlichen Körpern - Theorie und Implementation, PhD Thesis, Vorlesungen aus dem Fachbereich Mathematik der Universität GH Essen, Heft 28, Universität GH Essen, 2000. MR 2001m:11212
  • 8. E. Kaltofen and A. Lobo, Factoring high-degree polynomials by the black box Berlekamp algorithm, ISSAC '94 (J. von zur Gathen and M. Giesbrecht, eds.), 1994, pp. 90-98.
  • 9. E. Kaltofen and B.D. Saunders, On Wiedemann's method of solving sparse linear systems, Proc. AAECC-9, Lecture Notes in Computer Sci., vol. 539, Springer Verlag, 1991, pp. 29-38. MR 94b:68002
  • 10. E. Kaltofen and V. Shoup, Subquadratic-time factoring of polynomials over finite fields, Proc. 27th Annual ACM Symp. Theory of Comp., ACM Press, 1995, pp. 398-406; final version, Math. Comp. 67 (1998), 1179-1197. MR 99m:68097
  • 11. J.L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory 15 (1969), pp. 122-127. MR 39:3887
  • 12. M. Mignotte and D. Stefanescu, Polynomials: An Algorithmic Approach, Springer-Verlag, Singapore, 1999. MR 2000e:12001
  • 13. H. Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Applicable Algebra Engrg. Comm. Comput. 4 (1993), pp. 81-87. MR 94h:11112
  • 14. H. Niederreiter, New deterministic factorization algorithms for polynomials over finite fields, Contemp. Math. 168 (1994), pp. 251-268. MR 95f:11100
  • 15. H. Niederreiter and R. Göttfert, Factorizations of polynomials over finite fields and characteristic sequences, J. Symbolic Comput. 16 (1993), pp. 401-412. MR 95d:68072
  • 16. P. Roelse, Linear Methods for Polynomial Factorization over Finite Fields - Theory and Implementations, PhD Thesis, Vorlesungen aus dem Fachbereich Mathematik der Universität GH Essen, Heft 25, Universität GH Essen, 1997. MR 2000k:11142
  • 17. P. Roelse, Factoring high-degree polynomials over ${\mathbb F}_2$ with Niederreiter's algorithm on the IBM SP2, Math. Comp. 68 (1999), no. 226, pp. 869-880. MR 99i:11112
  • 18. D. Wan, Computing zeta functions over finite fields, Finite Fields: Theory, Applications, and Algorithms (R.C. Mullin and G.L. Mullen, eds.), Contemp. Math. 225, American Mathematical Society, 1999, pp. 131-142. MR 99j:11073
  • 19. D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), pp. 54-62. MR 87g:11166
  • 20. 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 (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

American Mathematical Society