Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Factoring polynomials over finite fields using differential equations and normal bases

Author: Harald Niederreiter
Journal: Math. Comp. 62 (1994), 819-830
MSC: Primary 11T06; Secondary 11Y16
MathSciNet review: 1216262
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853-1859. MR 0219231 (36:2314)
  • [2] I. Blake, X. H. Gao, A. Menezes, R. Mullin, S. Vanstone, and T. Yaghoobian, Applications of finite fields, Kluwer Acad. Publ., Boston, 1993.
  • [3] D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), 693-701. MR 1129288 (92i:68068)
  • [4] R. Göttfert, An acceleration of the Niederreiter factorization algorithm in characteristic 2, Math. Comp. 62 (1994), 831-839. MR 1218344 (94g:11110)
  • [5] 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.
  • [6] R. Lidl and H. Niederreiter, Finite fields, Addison-Wesley, Reading, MA, 1983. MR 746963 (86c:11106)
  • [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, preprint, 1992.
  • [9] R. C. Mullin, I. M. Onyszchuk, S. A. Vanstone, and R. M. Wilson, Optimal normal bases in $ GF({p^n})$, Discrete Appl. Math. 22 (1988/89), 149-161. MR 978054 (90c:11092)
  • [10] 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.
  • [11] -, A simple and general approach to the decimation of feedback shift-register sequences, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform. 17 (1988), 327-331. MR 967952 (89k:94054)
  • [12] -, 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)
  • [13] -, Factorization of polynomials and some linear-algebra problems over finite fields, Linear Algebra Appl. 192 (1993), 301-328. MR 1236747 (95b:11114)
  • [14] H. Niederreiter and R. Göttfert, Factorization of polynomials over finite fields and characteristic sequences, J. Symbolic Comput. (to appear). MR 1271081 (95d:68072)
  • [15] O. Teichmüller, Differentialrechnung bei Charakteristik p, J. Reine Angew. Math. 175 (1936), 89-99.

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, differential equations in rational function fields, normal bases
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society