Paper 2019/1493

Solving Xq+1+X+a=0 over Finite Fields

Kwang Ho Kim, Junyop Choe, and Sihem Mesnager

Abstract

Solving the equation Pa(X):=Xq+1+X+a=0 over 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 \cite{ACZ2000}, the construction of difference sets with Singer parameters \cite{DD2004}, determining cross-correlation between -sequences \cite{DOBBERTIN2006,HELLESETH2008} and to construct error-correcting 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 -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 identify all the -zeros, even in the case , it was solved only under the condition \cite{KM2019}. We discuss this equation without any restriction on and . New criteria for the number of the -zeros of are proved. For the cases of one or two -zeros, we provide explicit expressions for these rational zeros in terms of . For the case of rational zeros, we provide a parametrization of such 's and express the rational zeros by using that parametrization.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Contact author(s)
smesnager @ univ-paris8 fr
History
2019-12-30: received
Short URL
https://ia.cr/2019/1493
License
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2019/1493}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.