Welcome to the resource topic for 2021/011
Title:
Complete solution over \GF{p^n} of the equation X^{p^k+1}+X+a=0
Authors: Kwang Ho Kim, Jong Hyok Choe, Sihem Mesnager
Abstract:The problem of solving explicitly the equation P_a(X):=X^{q+1}+X+a=0 over the finite field \GF{Q}, where Q=p^n, q=p^k and p is a prime, arises in many different contexts including finite geometry, the inverse Galois problem \cite{ACZ2000}, the construction of difference sets with Singer parameters \cite{DD2004}, determining cross-correlation between m-sequences \cite{DOBBERTIN2006} and to construct error correcting codes \cite{Bracken2009}, cryptographic APN functions \cite{BTT2014,Budaghyan-Carlet_2006}, designs \cite{Tang_2019}, as well as to speed up the index calculus method for computing discrete logarithms on finite fields \cite{GGGZ2013,GGGZ2013+} and on algebraic curves \cite{M2014}. Subsequently, in \cite{Bluher2004,HK2008,HK2010,BTT2014,Bluher2016,KM2019,CMPZ2019,MS2019,KCM19}, the \GF{Q}-zeros of P_a(X) have been studied. In \cite{Bluher2004}, it was shown that the possible values of the number of the zeros that P_a(X) has in \GF{Q} is 0, 1, 2 or p^{\gcd(n, k)}+1. Some criteria for the number of the \GF{Q}-zeros of P_a(x) were found in \cite{HK2008,HK2010,BTT2014,KM2019,MS2019}. However, while the ultimate goal is to explicit all the \GF{Q}-zeros, even in the case p=2, it was solved only under the condition \gcd(n, k)=1 \cite{KM2019}. In this article, we discuss this equation without any restriction on p and \gcd(n,k). In \cite{KCM19}, for the cases of one or two \GF{Q}-zeros, explicit expressions for these rational zeros in terms of a were provided, but for the case of p^{\gcd(n, k)}+1 \GF{Q}- zeros it was remained open to explicitly compute the zeros. This paper solves the remained problem, thus now the equation X^{p^k+1}+X+a=0 over \GF{p^n} is completely solved for any prime p, any integers n and k.
ePrint: https://eprint.iacr.org/2021/011
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .