**Complete solution over $\GF{p^n}$ of the equation $X^{p^k+1}+X+a=0$**

*Kwang Ho Kim and Jong Hyok Choe and 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$.

**Category / Keywords: **foundations / Equation, Finite field, Zeros of a polynomial

**Date: **received 4 Jan 2021

**Contact author: **smesnager at univ-paris8 fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20210106:214004 (All versions of this report)

**Short URL: **ia.cr/2021/011

[ Cryptology ePrint archive ]