Remote Access Mathematics of Computation
Green Open Access

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?)

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

Article copyright: © Copyright 1969 American Mathematical Society