University of Surrey

Test tubes in the lab Research in the ATI Dance Research

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

Granger, Robert (2019) On the Enumeration of Irreducible Polynomials over GF(q) with Prescribed Coefficients Finite Fields and Their Applications, 57. pp. 156-229.

4andmorenewV6.pdf - Accepted version Manuscript

Download (620kB) | Preview


We present an efficient deterministic algorithm which outputs exact expressions in terms of n for the number of monic degree n irreducible polynomials over Fq of characteristic p for which the first l˂p coefficients are prescribed, provided that n is coprime to p. Each of these counts is 1n(qn−l + O(qn/2)). The main idea behind the algorithm is to associate to an equivalent problem a set of Artin-Schreier curves defined over Fq whose number of Fqn-rational affine points must be combined. This is accomplished by computing their zeta functions using a p-adic algorithm due to Lauder and Wan. Using the computational algebra system Magma one can, for example, compute the zeta functions of the arising curves for q=5 and l=4 very efficiently, and we detail a proof-of-concept demonstration. Due to the failure of Newton's identities in positive characteristic, the l≥p cases are seemingly harder. Nevertheless, we use an analogous algorithm to compute example curves for q=2 and l≤7, and for q=3 and l=3. Again using Magma, for q=2 we computed the relevant zeta functions for l=4 and l=5, obtaining explicit formulae for these open problems for n odd, as well as for subsets of these problems for all n, while for q=3 we obtained explicit formulae for l=3 and n coprime to 3. We also discuss some of the computational challenges and theoretical questions arising from this approach in the general case and propose some natural open problems.

Item Type: Article
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
Date : May 2019
DOI : 10.1016/j.ffa.2019.01.001
Copyright Disclaimer : © 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Uncontrolled Keywords : Irreducible polynomials; Prescribed coefficients; Prescribed traces; Artin-Schreier curves; Zeta functions; Binary Kloosterman sums
Depositing User : Clive Harris
Date Deposited : 25 Jan 2019 11:00
Last Modified : 16 Apr 2019 15:36

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800