Paper 2021/011

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

Kwang Ho Kim, 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 $\text{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 $$-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 $$-zeros of $$ have been studied. In \cite{Bluher2004}, it was shown that the possible values of the number of the zeros that $$ has in $$ is $$, $$, $$ or $$. Some criteria for the number of the $$-zeros of $$ were found in \cite{HK2008,HK2010,BTT2014,KM2019,MS2019}. However, while the ultimate goal is to explicit all the $$-zeros, even in the case $$, it was solved only under the condition $$ \cite{KM2019}. In this article, we discuss this equation without any restriction on $$ and $$. In \cite{KCM19}, for the cases of one or two $$-zeros, explicit expressions for these rational zeros in terms of $$ were provided, but for the case of $$ $$ zeros it was remained open to explicitly compute the zeros. This paper solves the remained problem, thus now the equation $$ over $$ is completely solved for any prime $$, any integers $$ and $$.