On the Enumeration of Irreducible Polynomials over GF(q) with Prescribed Coefficients

9 November 2016

Gauss was the first to give a formula for the number of monic irreducible polynomials of degree n over a finite field. A 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. In this talk I shall present an algorithm which for any finite field GF(q) of characteristic p expresses the number of monic irreducibles of degree n for which the first l < p coefficients are prescribed, for n >= l and coprime to p, in terms of the number of GF(q^n)-rational points of certain affine varieties defined over GF(q). 
The GF(2) base field case is related to the distribution of binary Kloosterman sums, which have numerous applications in coding theory and cryptography, for example via the construction of bent functions. Using a variant of the algorithm, we present varieties (which are all curves) for l <= 7 and compute explicit formulae for l <= 5; before this work such formulae were only known for l <= 3. While this connection motivates the problem, the talk shall focus mainly on computational algebraic geometry, with the algorithm, theoretical questions and computational challenges taking centre stage.

  • Cryptography Seminar