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. 156229.

Text
4andmorenewV6.pdf  Accepted version Manuscript Download (620kB)  Preview 
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(q^{n−l} + O(q^{n/2})). The main idea behind the algorithm is to associate to an equivalent problem a set of ArtinSchreier curves defined over F_{q} whose number of F_{qn}rational affine points must be combined. This is accomplished by computing their zeta functions using a padic 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 proofofconcept 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 CCBYNCND 4.0 license http://creativecommons.org/licenses/byncnd/4.0/  
Uncontrolled Keywords :  Irreducible polynomials; Prescribed coefficients; Prescribed traces; ArtinSchreier curves; Zeta functions; Binary Kloosterman sums  
Depositing User :  Clive Harris  
Date Deposited :  25 Jan 2019 11:00  
Last Modified :  16 Apr 2019 15:36  
URI:  http://epubs.surrey.ac.uk/id/eprint/850280 
Actions (login required)
View Item 
Downloads
Downloads per month over past year