Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



An acceleration of the Niederreiter factorization algorithm in characteristic $ 2$

Author: Rainer Göttfert
Journal: Math. Comp. 62 (1994), 831-839
MSC: Primary 11T06; Secondary 11Y16
MathSciNet review: 1218344
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A new deterministic factorization algorithm for polynomials over finite fields was recently developed by Niederreiter. The bottleneck in this algorithm is the last stage in which the irreducible factors of the polynomial are derived from the solutions of a system of linear equations. In this paper, we consider finite fields of characteristic 2, and we show that in this case there is a more efficient approach to the last stage of the Niederreiter algorithm, which speeds up the algorithm considerably.

References [Enhancements On Off] (What's this?)

  • [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1974. MR 0413592 (54:1706)
  • [2] D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), 693-701. MR 1129288 (92i:68068)
  • [3] P. Fleischmann, Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over $ {\mathbb{F}_q}$, Linear Algebra Appl. 192 (1993), 101-108. MR 1236738 (94f:11129)
  • [4] D. Yu. Grigoriev, Multiplicative complexity of a pair of bilinear forms and of the polynomial multiplication, Mathematical Foundations of Computer Science 1978 (J. Winkowski, ed.), Lecture Notes in Comput. Sci., vol. 64, Springer-Verlag, Berlin, 1978, pp. 250-256. MR 519843 (80d:68052)
  • [5] T. C. Y. Lee and S. A. Vanstone, Subspaces and polynomial factorizations over finite fields, Applicable Algebra in Engrg. Comm. Comp. (to appear). MR 1329362 (96b:11156)
  • [6] A. Lempel, G. Seroussi, and S. Winograd, On the complexity of multiplication in finite fields, Theoret. Comput. Sci. 22 (1983), 285-296. MR 693061 (84c:68031)
  • [7] M. Mignotte, Mathematics for computer algebra, Springer-Verlag, New York, 1992. MR 1140923 (92i:68071)
  • [8] V. S. Miller, On the factorization method of Niederreiter, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., 1992, preprint.
  • [9] H. Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Applicable Algebra in Engrg. Comm. Comp. 4 (1993), 81-87. MR 1223850 (94h:11112)
  • [10] -, Factorization of polynomials and some linear-algebra problems over finite fields, Linear Algebra Appl. 192 (1993), 301-328. MR 1236747 (95b:11114)
  • [11] -, Factoring polynomials over finite fields using differential equations and normal bases, Math. Comp. 62 (1994), 819-830. MR 1216262 (94g:11113)
  • [12] H. Niederreiter and R. Göttfert, Factorization of polynomials over finite fields and characteristic sequences, J. Symbolic Comput. (to appear). MR 1271081 (95d:68072)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T06, 11Y16

Retrieve articles in all journals with MSC: 11T06, 11Y16

Additional Information

Keywords: Polynomial factorization, finite fields of characteristic 2
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society