University of Surrey    # 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.  Preview
Text
4andmorenewV6.pdf - Accepted version Manuscript

## Abstract

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 :
NameEmailORCID
Granger, Robertr.granger@surrey.ac.uk
Date : May 2019
DOI : 10.1016/j.ffa.2019.01.001
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
URI: http://epubs.surrey.ac.uk/id/eprint/850280 View Item