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)

 

Factoring polynomials over large finite fields


Author: E. R. Berlekamp
Journal: Math. Comp. 24 (1970), 713-735
MSC: Primary 12.25; Secondary 94.00
MathSciNet review: 0276200
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper reviews some of the known algorithms for factoring polynomials over finite fields and presents a new deterministic procedure for reducing the problem of factoring an arbitrary polynomial over the Galois field $ {\text{GF}}({p^m})$ to the problem of finding the roots in $ {\text{GF}}(p)$ of certain other polynomials over $ {\text{GF}}(p)$. The amount of computation and the storage space required by these algorithms are algebraic in both the degree of the polynomial to be factored and the logarithm of the order of the finite field.

Certain observations on the application of these methods to the factorization of polynomials over the rational integers are also 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

DOI: http://dx.doi.org/10.1090/S0025-5718-1970-0276200-X
PII: S 0025-5718(1970)0276200-X
Keywords: Factorization, computation in finite fields, Kronecker algorithm, Hensel factorizations, root-finding, irreducibility criteria
Article copyright: © Copyright 1970 American Mathematical Society