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
- PDF | Request permission
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
- E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.1538-7305.1967.tb03174.x
- 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
- David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592. MR 606517, DOI 10.1090/S0025-5718-1981-0606517-5
- Peter Fleischmann, Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over $\textbf {F}_q$, Linear Algebra Appl. 192 (1993), 101–108. Computational linear algebra in algebraic and related problems (Essen, 1992). MR 1236738, DOI 10.1016/0024-3795(93)90238-J
- 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
- Shuhong Gao and Joachim von zur Gathen, Berlekamp’s and Niederreiter’s polynomial factorization algorithms, Finite fields: theory, applications, and algorithms (Las Vegas, NV, 1993) Contemp. Math., vol. 168, Amer. Math. Soc., Providence, RI, 1994, pp. 101–116. MR 1291420, DOI 10.1090/conm/168/01691
- Markus Chr. Holder, Arithmetik grossgradiger Polynome über kleinen endlichen Körpern, Vorlesungen aus dem Fachbereich Mathematik der Universität GH Essen [Lecture Notes in Mathematics at the University of Essen], vol. 28, Universität Essen, Fachbereich Mathematik, Essen, 2000 (German). Theorie und Implementation. [Theory and implementation]; Dissertation, Universität GH Essen, Essen, 2000. MR 1776563
- 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.
- H. F. Mattson, T. Mora, and T. R. N. Rao (eds.), Applied algebra, algebraic algorithms and error-correcting codes, Lecture Notes in Computer Science, vol. 539, Springer-Verlag, Berlin, 1991. MR 1229303, DOI 10.1007/3-540-54522-0
- Erich Kaltofen and Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179–1197. MR 1459389, DOI 10.1090/S0025-5718-98-00944-2
- James L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory IT-15 (1969), 122–127. MR 242556, DOI 10.1109/tit.1969.1054260
- Maurice Mignotte and Doru Ştefănescu, Polynomials, Springer Series in Discrete Mathematics and Theoretical Computer Science, Springer-Verlag Singapore, Singapore; Centre for Discrete Mathematics & Theoretical Computer Science, Auckland, 1999. An algorithmic approach. MR 1690362
- Harald Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 81–87. MR 1223850, DOI 10.1007/BF01386831
- 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
- Harald Niederreiter and Rainer Göttfert, Factorization of polynomials over finite fields and characteristic sequences, J. Symbolic Comput. 16 (1993), no. 5, 401–412. MR 1271081, DOI 10.1006/jsco.1993.1055
- Peter L. A. Roelse, Linear methods for polynomial factorization over finite fields, Vorlesungen aus dem Fachbereich Mathematik der Universität GH Essen [Lecture Notes in Mathematics at the University of Essen], vol. 25, Universität Essen, Fachbereich Mathematik, Essen, 1997. Theory and implementations; Dissertation, Universität-Gesamthochschule-Essen, Essen, 1997. MR 1723852
- Peter Roelse, Factoring high-degree polynomials over $\textbf {F}_2$ with Niederreiter’s algorithm on the IBM SP2, Math. Comp. 68 (1999), no. 226, 869–880. MR 1604383, DOI 10.1090/S0025-5718-99-01008-X
- Daqing Wan, Computing zeta functions over finite fields, Finite fields: theory, applications, and algorithms (Waterloo, ON, 1997) Contemp. Math., vol. 225, Amer. Math. Soc., Providence, RI, 1999, pp. 131–141. MR 1650604, DOI 10.1090/conm/225/03215
- Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, DOI 10.1109/TIT.1986.1057137
- D.Y.Y. Yun, On square-free decomposition algorithms, Proc. ACM Symp. Symbolic and Algebraic Comput. (R.D. Jenks, ed.), 1976, pp. 26–35.
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