An acceleration of the Niederreiter factorization algorithm in characteristic $2$
HTML articles powered by AMS MathViewer
- by Rainer Göttfert PDF
- Math. Comp. 62 (1994), 831-839 Request permission
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
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
- David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693–701. MR 1129288, DOI 10.1007/BF01178683
- 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
- D. Yu. Grigoriev, Multiplicative complexity of a pair of bilinear forms and of the polynomial multiplication, Mathematical foundations of computer science, 1978 (Proc. Seventh Sympos., Zakopane, 1978) Lecture Notes in Comput. Sci., vol. 64, Springer, Berlin-New York, 1978, pp. 250–256. MR 519843
- Therese C. Y. Lee and Scott A. Vanstone, Subspaces and polynomial factorizations over finite fields, Appl. Algebra Engrg. Comm. Comput. 6 (1995), no. 3, 147–157. MR 1329362, DOI 10.1007/BF01195333
- A. Lempel, G. Seroussi, and S. Winograd, On the complexity of multiplication in finite fields, Theoret. Comput. Sci. 22 (1983), no. 3, 285–296. MR 693061, DOI 10.1016/0304-3975(83)90108-1
- Maurice Mignotte, Mathematics for computer algebra, Springer-Verlag, New York, 1992. Translated from the French by Catherine Mignotte. MR 1140923, DOI 10.1007/978-1-4613-9171-5 V. S. Miller, On the factorization method of Niederreiter, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., 1992, preprint.
- 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, Factorization of polynomials and some linear-algebra problems over finite fields, Linear Algebra Appl. 192 (1993), 301–328. Computational linear algebra in algebraic and related problems (Essen, 1992). MR 1236747, DOI 10.1016/0024-3795(93)90247-L
- Harald Niederreiter, Factoring polynomials over finite fields using differential equations and normal bases, Math. Comp. 62 (1994), no. 206, 819–830. MR 1216262, DOI 10.1090/S0025-5718-1994-1216262-2
- 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
Additional Information
- © Copyright 1994 American Mathematical Society
- Journal: Math. Comp. 62 (1994), 831-839
- MSC: Primary 11T06; Secondary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-1994-1218344-8
- MathSciNet review: 1218344