Factorization of polynomials over finite fields
Author:
Robert J. McEliece
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
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
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.
-
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 https://doi.org/10.1002/j.1538-7305.1967.tb03174.x
- Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234
Retrieve articles in Mathematics of Computation with MSC: 12.25, 94.00
Retrieve articles in all journals with MSC: 12.25, 94.00
Additional Information
Article copyright:
© Copyright 1969
American Mathematical Society