Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On polynomial factorization over finite fields

Authors: Hiroshi Gunji and Dennis Arnon
Journal: Math. Comp. 36 (1981), 281-287
MSC: Primary 12-04
MathSciNet review: 595063
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ f(x)$ be a polynomial over a finite field F. An algorithm for determining the degrees of the factors of $ f(x)$ is presented. As in the Berlekamp algorithm (1968) for determining the factors of $ f(x)$, the Frobenius endomorphism on $ F[x]/(f(x))$ plays a central role. Little-known theorems of Schwarz (1956) and Cesàro (1888) provide the basis for the algorithm we present. New and stream-lined proofs of both theorems are provided.

References [Enhancements On Off] (What's this?)

  • [1] Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
  • [2] M. C. R. Butler, On the reducibility of polynomials over a finite field, Quart. J. Math., Oxford Ser. (2) 5 (1954), 102–107. MR 0062759
  • [3] L. Carlitz, Some matrices related to the greatest integer function, J. Elisha Mitchell Sci. Soc. 76 (1960), 5–7. MR 0123511
  • [4] David R. Musser, On the efficiency of a polynomial irreducibility test, J. Assoc. Comput. Mach. 25 (1978), no. 2, 271–282. MR 488309, 10.1145/322063.322071
  • [5] Štefan Schwarz, On the reducibility of polynomials over a finite field, Quart. J. Math. Oxford Ser. (2) 7 (1956), 110–124. MR 0096679
  • [6] S. Smith, "On the value of a certain arithmetical determinant," Proc. London Math. Soc., v. 7, 1876, pp. 208-212.
  • [7] B. L. van der Waerden, Algebra. Vol 1, Translated by Fred Blum and John R. Schulenberger, Frederick Ungar Publishing Co., New York, 1970. MR 0263582
  • [8] B. F. Wyman, What is a reciprocity law?, Amer. Math. Monthly 79 (1972), 571–586; correction, ibid. 80 (1973), 281. MR 0308084
  • [9] Horst G. Zimmer, Computational problems, methods, and results in algebraic number theory, Lecture Notes in Mathematics, Vol. 262, Springer-Verlag, Berlin-New York, 1972. MR 0323751

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12-04

Retrieve articles in all journals with MSC: 12-04

Additional Information

Keywords: Finite fields, polynomials, factorization, inversion formulas, integer matrices, Frobenius mapping
Article copyright: © Copyright 1981 American Mathematical Society