Roots of sparse polynomials over a finite field

DOI10.1112/S1461157016000334MaRDI QIDQ2971010zbMATHFDO

Authors Zander Kelley

Publication date 4 April 2017

Published in LMS Journal of Computation and Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Polynomials over finite fields (11T06)

Abstract: For a $t$-nomial $f(x)=su{m}_{i=1}^t{c}_i{x}^{a_i}inmathbb{F}_q[x]$, we show that the number of distinct, nonzero roots of $f$ is bounded above by $2(q-1{)}^{1-varepsilon}{C}^{v}arepsilon$, where $varepsilon=1/(t-1)$ and $C$ is the size of the largest coset in $mathbb{F}_q^{\ast }$ on which $f$ vanishes completely. Additionally, we describe a number-theoretic parameter depending only on $q$ and the exponents $a_i$ which provides a general and easily-computable upper bound for $C$. We thus obtain a strict improvement over an earlier bound of Canetti et al. which is related to the uniformity of the Diffie-Hellman distribution. Finally, we conjecture that $t$-nomials over prime fields have only $O(tlogp)$ roots in $mathbb{F}_p^{\ast }$ when $C=1$.

Recommendations

• Sparse univariate polynomials with many roots over finite fields
• On the number of distinct roots of a lacunary polynomial over finite fields
• Exponential sums with sparse polynomials over finite fields
• Estimating the number of roots of trinomials over finite fields
• Sublinear root detection and new hardness results for sparse polynomials over finite fields

Cites work

• On the correlation of binary \(M\)-sequences
• On the number of solutions of exponential congruences
• On the singularity of generalised Vandermonde matrices over finite fields
• On the statistical properties of Diffie-Hellman distributions
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields

Cited in

(12)

• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• On the number of distinct roots of a lacunary polynomial over finite fields
• Value sets of sparse polynomials
• Roots of certain polynomials over finite fields
• Randomized NP-completeness for p -adic rational roots of sparse polynomials in one variable
• Estimating the number of roots of trinomials over finite fields
• Taking roots over high extensions of finite fields
• Sparse polynomial equations and other enumerative problems whose Galois groups are wreath products
• scientific article; zbMATH DE number 5038555 (Why is no real title available?)
• Sparse univariate polynomials with many roots over finite fields
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• Sublinear root detection and new hardness results for sparse polynomials over finite fields

This page was built for publication: Roots of sparse polynomials over a finite field

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