General Factoring Algorithms for Polynomials over Finite Fields

In this paper, we generate algorithms for factoring polynomials with coefficients in finite fields. In particular, we develop one deterministic algorithm due to Elwyn Berlekamp and one probabilistic algorithm due to David Cantor and Hans Zassenhaus. While some authors present versions of the algorithms that can only factor polynomials of a certain form, the algorithms we give are able to factor any polynomial over any finite field. Hence, the algorithms we give are the most general algorithms available for this factorization problem. After formulating the algorithms, we look at various ways they can be applied to more specialized inquiries. For example, we use the algorithms to develop two tests for irreducibility and a process for finding the roots of a polynomial over a finite field. We conclude our work by considering how the Berlekamp and Cantor-Zassenhaus methods can be combined to develop a more efficient factoring process