|
The black-box Niederreiter algorithm and its implementation over the binary field
Author(s):
Peter
Fleischmann;
Markus
Chr.
Holder;
Peter
Roelse.
Journal:
Math. Comp.
72
(2003),
1887-1899.
MSC (2000):
Primary 11-04, 11T06, 11Y16
Posted:
April 21, 2003
Retrieve article in:
PDF DVI PostScript
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:
- 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
 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
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
DOI:
10.1090/S0025-5718-03-01494-7
PII:
S 0025-5718(03)01494-7
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
Posted:
April 21, 2003
Copyright of article:
Copyright
2003,
American Mathematical Society
|
Comments: webmaster@ams.org