New Algorithms for Finding Irreducible Polynomials Over Finite Fields

Abstract

We present a new algorithm for finding an irreducible polynomial of specified degree over a finite field. Our algorithm is deterministic, and it runs in polynomial time for fields of small characteristic. We in fact prove the stronger result that the problem of finding irreducible polynomials of specified degree over a finite field is deterministic polynomial-time reducible to the problem of factoring polynomials over the prime field.