Factoring polynomials over finite fields using differential equations and normal bases
HTML articles powered by AMS MathViewer
- by Harald Niederreiter PDF
- Math. Comp. 62 (1994), 819-830 Request permission
Abstract:
The deterministic factorization algorithm for polynomials over finite fields that was recently introduced by the author is based on a new type of linearization of the factorization problem. The main ingredients are differential equations in rational function fields and normal bases of field extensions. For finite fields of characteristic 2, it is known that this algorithm has several advantages over the classical Berlekamp algorithm. We develop the algorithm in a general framework, and we show that it is feasible for arbitrary finite fields, in the sense that the linearization can be achieved in polynomial time.References
- E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.1538-7305.1967.tb03174.x I. Blake, X. H. Gao, A. Menezes, R. Mullin, S. Vanstone, and T. Yaghoobian, Applications of finite fields, Kluwer Acad. Publ., Boston, 1993.
- 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
- Rainer Göttfert, An acceleration of the Niederreiter factorization algorithm in characteristic $2$, Math. Comp. 62 (1994), no. 206, 831–839. MR 1218344, DOI 10.1090/S0025-5718-1994-1218344-8 H. Hasse, Theorie der höheren Differentiale in einem algebraischen Funktionenkörper mit vollkommenem Konstantenkörper bei beliebiger Charakteristik, J. Reine Angew. Math. 175 (1936), 50-54.
- 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
- 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, preprint, 1992.
- R. C. Mullin, I. M. Onyszchuk, S. A. Vanstone, and R. M. Wilson, Optimal normal bases in $\textrm {GF}(p^n)$, Discrete Appl. Math. 22 (1988/89), no. 2, 149–161. MR 978054, DOI 10.1016/0166-218X(88)90090-X H. Niederreiter, Sequences with almost perfect linear complexity profile, Advances in Cryptology—EUROCRYPT ’87 (D. Chaum and W. L. Price, eds.), Lecture Notes in Comput. Sci., vol. 304, Springer-Verlag, Berlin, 1988, pp. 37-51.
- H. Niederreiter, A simple and general approach to the decimation of feedback shift-register sequences, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform. 17 (1988), no. 5, 327–331 (English, with Russian summary). MR 967952
- 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 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 O. Teichmüller, Differentialrechnung bei Charakteristik p, J. Reine Angew. Math. 175 (1936), 89-99.
Additional Information
- © Copyright 1994 American Mathematical Society
- Journal: Math. Comp. 62 (1994), 819-830
- MSC: Primary 11T06; Secondary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-1994-1216262-2
- MathSciNet review: 1216262