Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields

DOI10.1145/2465506.2465514zbMATH Open1360.68916arXiv1204.1113OpenAlexW2132291283MaRDI QIDQ2963217FDOQ2963217

Authors: Jingguo Bi, Qi Cheng, J. Maurice Rojas 

Publication date: 10 February 2017

Published in: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Abstract: We present a deterministic 2^O(t)q^{(t-2)(t-1)+o(1)} algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree <q, has a root in F_q. A corollary of our method --- the first with complexity sub-linear in q when t is fixed --- is that the nonzero roots in F_q can be partitioned into at most 2 sqrt{t-1} (q-1)^{(t-2)(t-1)} cosets of two subgroups S_1,S_2 of F^*_q, with S_1 in S_2. Another corollary is the first deterministic sub-linear algorithm for detecting common degree one factors of k-tuples of t-nomials in F_q[x] when k and t are fixed. When t is not fixed we show that each of the following problems is NP-hard with respect to BPP-reductions, even when p is prime: (1) detecting roots in F_p for f, (2) deciding whether the square of a degree one polynomial in F_p[x] divides f, (3) deciding whether the discriminant of f vanishes, (4) deciding whether the gcd of two t-nomials in F_p[x] has positive degree. Finally, we prove that if the complexity of root detection is sub-linear (in a refined sense), relative to the straight-line program encoding, then NEXP is not in P/Poly.

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

Recommendations

• Sublinear root detection and new hardness results for sparse polynomials over finite fields
• Faster \(p\)-adic feasibility for certain multivariate sparse polynomials
• Roots of sparse polynomials over a finite field
• Faster real feasibility via circuit discriminants
• Sparse univariate polynomials with many roots over finite fields

zbMATH Keywords

discriminantfinite fieldsNP-hardnesssolvabilityresultantsparse polynomialgcdsquare-free

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Cited In (13)

• Roots of sparse polynomials over a finite field
• Finding roots of a multivariate polynomial in a linear subspace
• Computing the multilinear factors of lacunary polynomials without heights
• Randomized NP-completeness for p -adic rational roots of sparse polynomials in one variable
• Estimating the number of roots of trinomials 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
• The number of roots of a lacunary bivariate polynomial on a line
• Faster \(p\)-adic feasibility for certain multivariate sparse polynomials
• Bounded-degree factors of lacunary multivariate polynomials
• Real roots of univariate polynomials and straight line programs
• Efficient zero-knowledge arguments and digital signatures \textit{via} sharing conversion \textit{in the head}
• Sublinear root detection and new hardness results for sparse polynomials over finite fields

This page was built for publication: Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields

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