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

DOI10.1016/J.FFA.2020.101797MaRDI QIDQ1995227zbMATH OpenOpenAlexFDO

Authors Kwang Ho Kim, Junyop Choe, Sihem Mesnager

Publication date 19 February 2021

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

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

zbMATH Keywords

equationfinite fieldsprojective polynomialzeros of a polynomial

Mathematics Subject Classification ID

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

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.

Review text

The authors study the equation \(P_{a}(X):=X^{q+1}+X+a=0\) over a finite field \(\mathbb F_{Q}\), where \(Q=p^n, q=p^k, p\) is a prime and \(a\in \mathbb F_{Q}^{\star}\). There are many papers devoted to finding the \(\mathbb F_{Q}\)-roots of \(P_{a}(X)\) as this equation arises in a natural way in some problems related to Galois theory, finite geometries, construction of error-correcting codes etc. It was proved by A. W. Bluher that the number \(N_a\) of \(\mathbb F_{Q}\)-roots of \(P_a(X)\) is \(0, 1, 2\) or \(p^{\gcd(n, k)}+1\) and later a series of criteria were found by other authors for the number \(N_a\). The problem of describing all \(\mathbb F_{Q}\)-roots of \(P_a(X)\) was solved only for \(p=2\) and \(\gcd(n, k)=1\) by K. H. Kim and S. Mesnager. In this paper, the authors obtained (without any restriction on \(p\) and \(\gcd(n, k)\)) new criteria for the number \(N_a\) and give explicit expressions for the roots in cases of 1 or 2 \(\mathbb F_Q\)-roots. They also pointed out a parametrization of the coefficients \(a^{,}s\) and expressed all the roots using this parametrization in case of \(p^{\gcd(n, k)}+1\) rational \(\mathbb F_{Q}\)-roots.

Recommendations

• Complete solution over \(\mathbb{F}_{p^n}\) of the equation \(X^{p^k+1}+X+a=0\)
• scientific article; zbMATH DE number 4148230
• Solving \(x^{2^k + 1} + x + a = 0\) in \(\mathbb{F}_{2^n}\) with \(\gcd(n, k) = 1\)
• On the number of solutions of the equation \(a_1x_1^{m_1} + \cdots +a_nx_n^{m_n} = bx_1 \cdots x_n\) in a finite field
• On \(x^{q+1}+ax+b\)

Cites work

• \(X^{2^l+1}+x+a\) and related affine polynomials over \(\mathrm{GF}(2^k\))
• A characterization of linearized polynomials with maximum kernel
• A characterization of the number of roots of linearized and projective polynomials in the field of coefficients
• Bivariate factorizations connecting Dickson polynomials and Galois theory
• Characterization of $m$-Sequences of Lengths $2^{2k}-1$ and $2^{k}-1$ With Three-Valued Cross Correlation
• Composition collisions and projective polynomials: statement of results
• New cyclic difference sets with Singer parameters
• Niho type cross-correlation functions via dickson polynomials and Kloosterman sums
• On \(x^{q+1}+ax+b\)
• On a class of quadratic polynomials with no zeros and its application to APN functions
• On the equation \(x^{2^l+1}+x+a=0\) over \(\mathrm{GF}(2^k)\)
• On the function field sieve and the impact of higher splitting probabilities. Application to discrete logarithms in \(\mathbb{F}_{2^{1971}}\) and \(\mathbb{F}_{2^{3164}}\)
• Projective polynomials
• 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\)
• Solving a 6120 -bit DLP on a Desktop Computer

Cited in

(25)

• Preimages of \(p\)-linearized polynomials over \(\mathbb{F}_p\)
• Classification of fractional projective permutations over finite fields
• Survey on recent trends towards generalized differential and boomerang uniformities
• Twisted linearized Reed-Solomon codes: a skew polynomial framework
• Complete solution over \(\mathbb{F}_{p^n}\) of the equation \(X^{p^k+1}+X+a=0\)
• Solving \(x^{2^k + 1} + x + a = 0\) in \(\mathbb{F}_{2^n}\) with \(\gcd(n, k) = 1\)
• On the equation \(x^{2^l+1}+x+a=0\) over \(\mathrm{GF}(2^k)\)
• On permutation quadrinomials with boomerang uniformity 4 and the best-known nonlinearity
• Completely characterizing a class of permutation quadrinomials
• scientific article; zbMATH DE number 3948428 (Why is no real title available?)
• On \(x^{q+1}+ax+b\)
• Evaluation of Weil sums for some polynomials and associated quadratic forms
• Roots of certain polynomials over finite fields
• Algebraic approach to the completeness problem for \((k,n)\)-arcs in planes over finite fields
• Factorization of invariant polynomials under actions of projective linear groups and its applications in coding theory
• Quadratic bent functions and their duals
• On the packing density of Lee spheres
• Exceptional scattered sequences
• On two conjectures of the duals of AMDS BCH codes
• Permutation polynomials and finite projective spaces
• Irreducible factorizations of polynomials \(x^{p^k + 1} - bx + b\) over a finite field
• Ovoids in the cyclic presentation of \(\mathrm{PG}(3, q)\)
• On the solutions of \(X^{q^2}+aX^q +bX=c\) over \(\mathbb{F}_{2^n}\)
• On the stability of \(b^q (x+a)^{q+1}+x\) from the perspective of periodic sequences
• Non-existence of infinite APN families from patched monomials in odd characteristic

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)