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 be a polynomial over a finite field *F*. An algorithm for determining the degrees of the factors of is presented. As in the Berlekamp algorithm (1968) for determining the factors of , the Frobenius endomorphism on 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.

**[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**

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

Retrieve articles in all journals with MSC: 12-04

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1981-0595063-3

Keywords:
Finite fields,
polynomials,
factorization,
inversion formulas,
integer matrices,
Frobenius mapping

Article copyright:
© Copyright 1981
American Mathematical Society