On polynomial factorization over finite fields

Gunji, Hiroshi; Arnon, Dennis

doi:10.1090/S0025-5718-1981-0595063-3

On polynomial factorization over finite fields
HTML articles powered by AMS MathViewer

by Hiroshi Gunji and Dennis Arnon PDF

Math. Comp. 36 (1981), 281-287 Request permission

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

Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
M. C. R. Butler, On the reducibility of polynomials over a finite field, Quart. J. Math. Oxford Ser. (2) 5 (1954), 102–107. MR 62759, DOI 10.1093/qmath/5.1.102
L. Carlitz, Some matrices related to the greatest integer function, J. Elisha Mitchell Sci. Soc. 76 (1960), 5–7. MR 123511
David R. Musser, On the efficiency of a polynomial irreducibility test, J. Assoc. Comput. Mach. 25 (1978), no. 2, 271–282. MR 488309, DOI 10.1145/322063.322071
Štefan Schwarz, On the reducibility of polynomials over a finite field, Quart. J. Math. Oxford Ser. (2) 7 (1956), 110–124. MR 96679, DOI 10.1093/qmath/7.1.110

Proc. London Math. Soc.

B. L. van der Waerden, Algebra. Vol 1, Frederick Ungar Publishing Co., New York, 1970. Translated by Fred Blum and John R. Schulenberger. MR 0263582
B. F. Wyman, What is a reciprocity law?, Amer. Math. Monthly 79 (1972), 571–586; correction, ibid. 80 (1973), 281. MR 308084, DOI 10.2307/2317083
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