On the Enumeration of Irreducible Polynomials over Finite Fields with Prescribed Coefficients

Colloquium:

Speaker: Robert Granger (Surrey, Computing) 

Abstract: Gauss was the first to give a formula for the number of monic irreducible polynomials of degree n over a finite field. A very natural problem is to determine the number of such polynomials for which certain coefficients are prescribed. While some asymptotic and existence results have been obtained, very few exact results are known. Over the base field GF(2), exact results for when the first three coefficients are prescribed were proven in 2001, but the four and more coefficient cases remained open. In this talk I shall describe a curve-based approach with which one can compute the desired formulae for odd n when up to the first seven coefficients are prescribed, and for all n for a subset of these cases. The GF(2) base field case is particularly interesting as it is related to the distribution of binary Kloosterman sums, which have numerous applications in coding theory and cryptography, such as the construction of bent functions, for example. Although the approach seemingly fails for eight coefficients, it generalises to arbitrary finite fields when the first l coefficients are prescribed, provided that l is less than the characteristic. We shall also briefly discuss some theoretical questions and computational challenges which arise from this approach.