2021/01/04 by Kwang Ho Kim, Kim, Kwang Ho, Jong Hyok Choe +3
Computer Science · Engineering · #12E05 #12E10 #12E12 #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Information Theory (cs.IT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2101.01003
openalex publication_date 2021/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of solving explicitly the equation Pa(X):=Xq+1+X+a=0 over the finite field \GFQ, where Q=pn, q=pk and p is a prime, arises in many different contexts including finite geometry, the inverse Galois problem \citeACZ2000, the construction of difference sets with Singer parameters \citeDD2004, determining cross-correlation between m-sequences \citeDOBBERTIN2006 and to construct error correcting codes \citeBracken2009, cryptographic APN functions \citeBTT2014,Budaghyan-Carlet2006, designs \citeTang2019, as well as to speed up the index calculus method for computing discrete logarithms on finite fields \citeGGGZ2013,GGGZ2013+ and on algebraic curves \citeM2014. Subsequently, in \citeBluher2004,HK2008,HK2010,BTT2014,Bluher2016,KM2019,CMPZ2019,MS2019,KCM19, the \GFQ-zeros of Pa(X) have been studied. In \citeBluher2004, it was shown that the possible values of the number of the zeros that Pa(X) has in \GFQ is 0, 1, 2 or pgcd(n, k)+1. Some criteria for the number of the \GFQ-zeros of Pa(x) were found in \citeHK2008,HK2010,BTT2014,KM2019,MS2019. However, while the ultimate goal is to explicit all the \GFQ-zeros, even in the case p=2, it was solved only under the condition gcd(n, k)=1 \citeKM2019. In this article, we discuss this equation without any restriction on p and gcd(n,k). In \citeKCM19, for the cases of one or two \GFQ-zeros, explicit expressions for these rational zeros in terms of a were provided, but for the case of pgcd(n, k)+1 \GFQ- zeros it was remained open to explicitly compute the zeros. This paper solves the remained problem, thus now the equation Xpk+1+X+a=0 over \GFpn is completely solved for any prime p, any integers n and k.