Solving X^q+1+X+a=0 over finite fields

DOI10.1016/J.FFA.2020.101797zbMATH Open1476.12001arXiv1912.12648OpenAlexW3003703995MaRDI QIDQ1995227FDOQ1995227

Kwang Ho Kim, Junyop Choe, Sihem Mesnager

Publication date: 19 February 2021

Published in: Finite Fields and their Applications (Search for Journal in Brave)

Abstract: Solving the equation $P_a(X):=X^{q+1}+X+a=0$ over finite field $GFQ$, 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,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 $GFQ$-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 $GFQ$ is $0$, $1$, $2$ or $p^{gcd(n,k)}+1$. Some criteria for the number of the $GFQ$-zeros of $P_a(x)$ were found in cite{HK2008,HK2010,BTT2014,KM2019,MS2019}. However, while the ultimate goal is to identify all the $GFQ$-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 $GFQ$-zeros of $P_a(x)$ are proved. For the cases of one or two $GFQ$-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.

Full work available at URL: https://arxiv.org/abs/1912.12648

zbMATH Keywords

equationfinite fieldszeros of a polynomialprojective polynomial

Mathematics Subject Classification ID

Polynomials in general fields (irreducibility, etc.) (12E05) Special polynomials in general fields (12E10) Equations in general fields (12E12)

Cites Work

• On the Function Field Sieve and the Impact of Higher Splitting Probabilities
• On \(x^{q+1}+ax+b\)
• New cyclic difference sets with Singer parameters
• Niho type cross-correlation functions via dickson polynomials and Kloosterman sums
• \(X^{2^l+1}+x+a\) and related affine polynomials over \(\mathrm{GF}(2^k\))
• On the equation \(x^{2^l+1}+x+a=0\) over \(\mathrm{GF}(2^k)\)
• Composition collisions and projective polynomials
• Projective polynomials
• Bivariate factorizations connecting Dickson polynomials and Galois theory
• A characterization of linearized polynomials with maximum kernel
• Characterization of $m$-Sequences of Lengths $2^{2k}-1$ and $2^{k}-1$ With Three-Valued Cross Correlation
• Solving a $$6120$$ -bit DLP on a Desktop Computer
• On a class of quadratic polynomials with no zeros and its application to APN functions
• A characterization of the number of roots of linearized and projective polynomials in the field of coefficients
• Solving \(x+x^{2^l}+\ldots +x^{2^{ml}}=a\) over \(\mathbb{F}_{2^n} \)
• Solving \(x^{2^k + 1} + x + a = 0\) in \(\mathbb{F}_{2^n}\) with \(\gcd(n, k) = 1\)

Cited In (14)

• Twisted linearized Reed-Solomon codes: a skew polynomial framework
• Quadratic bent functions and their duals
• Preimages of \(p\)-linearized polynomials over \(\mathbb{F}_p\)
• Classification of fractional projective permutations over finite fields
• On the packing density of Lee spheres
• Survey on recent trends towards generalized differential and boomerang uniformities
• Complete solution over \(\mathbb{F}_{p^n}\) of the equation \(X^{p^k+1}+X+a=0\)
• Roots of certain polynomials over finite fields
• Exceptional scattered sequences
• Algebraic approach to the completeness problem for \((k,n)\)-arcs in planes over finite fields
• On permutation quadrinomials with boomerang uniformity 4 and the best-known nonlinearity
• Completely characterizing a class of permutation quadrinomials
• Factorization of invariant polynomials under actions of projective linear groups and its applications in coding theory
• Evaluation of Weil sums for some polynomials and associated quadratic forms

This page was built for publication: Solving \(X^{q+1}+X+a=0\) over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1995227)