On a new factorization algorithm for polynomials over finite fields

Niederreiter, Harald; Göttfert, Rainer

doi:10.1090/S0025-5718-1995-1265019-6

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6842(online) ISSN 0025-5718(print)

On a new factorization algorithm for polynomials over finite fields

Authors: Harald Niederreiter and Rainer Göttfert
Journal: Math. Comp. 64 (1995), 347-353
MSC: Primary 11T06; Secondary 11Y16
MathSciNet review: 1265019
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 the first author. 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. An efficient approach to the last stage was designed by the second author for the case of finite fields of characteristic 2. In this paper, we describe a different approach to the last stage which works for arbitrary fields of positive characteristic. In particular, we obtain in this way an acceleration of the factorization algorithm of the first author which makes this algorithm polynomial time for fixed characteristic.

[1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR 0413592 (54 #1706)
[2] Peter Fleischmann, Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over 𝐹_{𝑞}, Linear Algebra Appl. 192 (1993), 101–108. Computational linear algebra in algebraic and related problems (Essen, 1992). MR 1236738 (94f:11129), http://dx.doi.org/10.1016/0024-3795(93)90238-J
[3] Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071 (94d:12011), http://dx.doi.org/10.1007/BF01272074
[4] Rainer Göttfert, An acceleration of the Niederreiter factorization algorithm in characteristic 2, Math. Comp. 62 (1994), no. 206, 831–839. MR 1218344 (94g:11110), http://dx.doi.org/10.1090/S0025-5718-1994-1218344-8
[5] 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 (96b:11156), http://dx.doi.org/10.1007/BF01195333
[6] Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963 (86c:11106)
[7] Maurice Mignotte, Mathematics for computer algebra, Springer-Verlag, New York, 1992. Translated from the French by Catherine Mignotte. MR 1140923 (92i:68071)
[8] V. S. Miller, On the factorization method of Niederreiter, preprint, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., 1992.
[9] 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 (94h:11112), http://dx.doi.org/10.1007/BF01386831
[10] 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 (95b:11114), http://dx.doi.org/10.1016/0024-3795(93)90247-L
[11] Harald Niederreiter, Factoring polynomials over finite fields using differential equations and normal bases, Math. Comp. 62 (1994), no. 206, 819–830. MR 1216262 (94g:11113), http://dx.doi.org/10.1090/S0025-5718-1994-1216262-2
[12] 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 (95f:11100), http://dx.doi.org/10.1090/conm/168/01705
[13] 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 (95d:68072), http://dx.doi.org/10.1006/jsco.1993.1055
[14] Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267. MR 1049276 (91f:11088), http://dx.doi.org/10.1016/0020-0190(90)90195-4
[15] Igor E. Shparlinski, Computational and algorithmic problems in finite fields, Mathematics and its Applications (Soviet Series), vol. 88, Kluwer Academic Publishers Group, Dordrecht, 1992. MR 1249064 (94j:11122)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|