Algebra Commons^™

Polynomial Factoring Algorithms And Their Computational Complexity, Nicholas Cavanna

Honors Scholar Theses

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 …