Polynomial Factoring Algorithms and their Computational Complexity

Finite fields, and the polynomial rings over them, have many neat algebraic properties and identities that are very convenient to work with. In this paper we will start by exploring said properties with the goal in mind of being able to use said properties to efficiently irreducibly factorize polynomials over these fields, an important action in the fields of discrete mathematics and computer science. Necessarily, we must also introduce the concept of an algorithm’s speed as well as particularly speeds of basic modular and integral arithmetic opera- tions. Outlining these concepts will have laid the groundwork for us to introduce the Berlekamp algorithm, as well as the Cantor-Zassenhaus algorithm: two dif- ferent approaches to the problem of factoring polynomials over finite fields, both in the algebraic properties the utilize as well as how the algorithms actually op- erate. This will lead us to a much harder problem, factoring polynomials over the integers. We will explain and prove how an elegant solution to this problem is directly related to finding the shortest vector in a lattice which also happens to use factoring over finite fields as a starting point. To conclude, we will give an efficient algorithm for factoring polynomials over the integers that circumvents the shortest vector requirement via an approximate solution, the LLL lattice basis reduction algorithm