On a new factorization algorithm for polynomials over finite fields
Authors:
Harald Niederreiter and Rainer Göttfert
Journal:
Math. Comp. 64 (1995), 347353
MSC:
Primary 11T06; Secondary 11Y16
MathSciNet review:
1265019
Fulltext 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,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Second printing; AddisonWesley 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/00243795(93)90238J
 [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/S00255718199412183448
 [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, AddisonWesley 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, SpringerVerlag,
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 linearalgebra
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/00243795(93)90247L
 [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/S00255718199412162622
 [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/00200190(90)901954
 [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)
 [1]
 A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, AddisonWesley, Reading, Mass., 1974. MR 0413592 (54:1706)
 [2]
 P. Fleischmann, Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over , Linear Algebra Appl. 192 (1993), 101108. MR 1236738 (94f:11129)
 [3]
 J. von zur Gathen and V. Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), 187224. MR 1220071 (94d:12011)
 [4]
 R. Göttfert, An acceleration of the Niederreiter factorization algorithm in characteristic 2, Math. Comp. 62 (1994), 831839. MR 1218344 (94g:11110)
 [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]
 R. Lidl and H. Niederreiter, Finite fields, AddisonWesley, Reading, Mass., 1983. MR 746963 (86c:11106)
 [7]
 M. Mignotte, Mathematics for computer algebra, SpringerVerlag, New York, 1992. 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]
 H. Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Applicable Algebra in Engrg. Comm. Comp. 4 (1993), 8187. MR 1223850 (94h:11112)
 [10]
 , Factorization of polynomials and some linearalgebra problems over finite fields, Linear Algebra Appl. 192 (1993), 301328. MR 1236747 (95b:11114)
 [11]
 , Factoring polynomials over finite fields using differential equations and normal bases, Math. Comp. 62 (1994), 819830. MR 1216262 (94g:11113)
 [12]
 , New deterministic factorization algorithms for polynomials over finite fields, Finite Fields: Theory, Applications, and Algorithms (G.L. Mullen and P.J.S. Shiue, eds.), Contemporary Mathematics, American Math. Society, Providence, R.I. (to appear). MR 1291434 (95f:11100)
 [13]
 H. Niederreiter and R. Göttfert, Factorization of polynomials over finite fields and characteristic sequences, J. Symbolic Comput. 16 (1993), 401412. MR 1271081 (95d:68072)
 [14]
 V. Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), 261267. MR 1049276 (91f:11088)
 [15]
 I. E. Shparlinski, Computational and algorithmic problems in finite fields, Kluwer, Dordrecht, 1993. MR 1249064 (94j:11122)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11T06,
11Y16
Retrieve articles in all journals
with MSC:
11T06,
11Y16
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718199512650196
PII:
S 00255718(1995)12650196
Keywords:
Polynomial factorization,
finite fields,
arithmetic complexity
Article copyright:
© Copyright 1995
American Mathematical Society
