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
DOI: https://doi.org/10.1090/S0025-5718-1981-0595063-3
MathSciNet review: 595063
Full-text PDF Free Access

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

DOI: https://doi.org/10.1090/S0025-5718-1981-0595063-3
Keywords: Finite fields, polynomials, factorization, inversion formulas, integer matrices, Frobenius mapping
Article copyright: © Copyright 1981 American Mathematical Society