Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On polynomial factorization over finite fields

Authors: Hiroshi Gunji and Dennis Arnon
Journal: Math. Comp. 36 (1981), 281-287
MSC: Primary 12-04
MathSciNet review: 595063
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12-04

Retrieve articles in all journals with MSC: 12-04

Additional Information

Keywords: Finite fields, polynomials, factorization, inversion formulas, integer matrices, Frobenius mapping
Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society