Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Factorization of polynomials over finite fields


Author: Robert J. McEliece
Journal: Math. Comp. 23 (1969), 861-867
MSC: Primary 12.25; Secondary 94.00
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.


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

  • [1] 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.
  • [2] E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 0219231 (36 #2314)
  • [3] Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234 (33 #5416)

Similar Articles

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

DOI: http://dx.doi.org/10.1090/S0025-5718-1969-0257039-X
PII: S 0025-5718(1969)0257039-X
Article copyright: © Copyright 1969 American Mathematical Society