Paper 2019/1493
Solving $X^{q+1}+X+a=0$ over Finite Fields
Kwang Ho Kim, Junyop Choe, and Sihem Mesnager
Abstract
Solving the equation $P_a(X):=X^{q+1}+X+a=0$ over 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 crosscorrelation between $m$sequences \cite{DOBBERTIN2006,HELLESETH2008} and to construct errorcorrecting codes \cite{Bracken2009}, 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}, 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 identify all the $\GF{Q}$zeros, even in the case $p=2$, it was solved only under the condition $\gcd(n, k)=1$ \cite{KM2019}. We discuss this equation without any restriction on $p$ and $\gcd(n,k)$. New criteria for the number of the $\GF{Q}$zeros of $P_a(x)$ are proved. For the cases of one or two $\GF{Q}$zeros, we provide explicit expressions for these rational zeros in terms of $a$. For the case of $p^{\gcd(n, k)}+1$ rational zeros, we provide a parametrization of such $a$'s and express the $p^{\gcd(n, k)}+1$ rational zeros by using that parametrization.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Contact author(s)
 smesnager @ univparis8 fr
 History
 20191230: received
 Short URL
 https://ia.cr/2019/1493
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/1493, author = {Kwang Ho Kim and Junyop Choe and Sihem Mesnager}, title = {Solving $X^{q+1}+X+a=0$ over Finite Fields}, howpublished = {Cryptology ePrint Archive, Paper 2019/1493}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/1493}}, url = {https://eprint.iacr.org/2019/1493} }