Roots of sparse polynomials over a finite field

DOI10.1112/S1461157016000334zbMATH Open1391.11154arXiv1602.00208MaRDI QIDQ2971010FDOQ2971010

Authors: Zander Kelley 

Publication date: 4 April 2017

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

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^{*}$ 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^{*}$ when $C=1$.

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

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

Mathematics Subject Classification ID

Polynomials over finite fields (11T06)

Cites Work

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

Cited In (12)

• Taking roots over high extensions of finite fields
• Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
• Randomized NP-completeness for p -adic rational roots of sparse polynomials in one variable
• Value Sets of Sparse Polynomials
• Estimating the number of roots of trinomials over finite fields
• Roots of certain polynomials over finite fields
• On the number of distinct roots of a lacunary polynomial over finite fields
• Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
• Sparse univariate polynomials with many roots over finite fields
• Sparse polynomial equations and other enumerative problems whose Galois groups are wreath products
• Title not available (Why is that?)
• 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)