Fast Construction of Irreducible Polynomials over Finite Fields

The main result of this paper a new algorithm for constructing an irreducible polynomial of specified degree n over a finite field Fq . The algorithm is probabilistic, and is asymptotically faster than previously known algorithms for this problem. It uses an expected number of O-(n2 + n log q) operations in Fq, where the "soft-O" O- indicates an implicit factor of (log n )O(1). In addition, two new polynomial irreducibility tests are described.