Factorization of polynomials over finite fields
HTML articles powered by AMS MathViewer
- by Robert J. McEliece PDF
- Math. Comp. 23 (1969), 861-867 Request permission
Abstract:
If $f(x)$ is a polynomial over $GF(q)$, we observe (as has Berlekamp) that if $h{(x)^q} \equiv h(x)(\bmod f(x))$, then $f(x) = \prod {{{_a}_{ \in GF(q)}}\gcd (f(x),h(x) - a)}$. The object of this paper is to give an explicit construction of enough such $h$’s so that the repeated application of this result will succeed in separating all irreducible factors of $f$. The $h$’s chosen are loosely defined by ${h_i}(x) \equiv {x^i} + {x^{iq}} + {x^{i{q^2}}} + \cdots (\bmod f(x))$. A detailed example over $GF(2)$ is given, and a table of the factors of the cyclotomic polynomials ${\Phi _n}(x)(\bmod p){\text { for }}p = 2,n \leqq 250;p = 3,n \leqq 100;p = 5,7,n \leqq 50$, is included.References
-
R. W. Marsh, Table of Irreducible Polynomials over $GF(2)$ through Degree 19, NSA, U.S. Department of Commerce, Office of Tech. Service, Washington, D.C., 1951.
- 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
- Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234
Additional Information
- © Copyright 1969 American Mathematical Society
- Journal: Math. Comp. 23 (1969), 861-867
- MSC: Primary 12.25; Secondary 94.00
- DOI: https://doi.org/10.1090/S0025-5718-1969-0257039-X
- MathSciNet review: 0257039