SCIENCE@home

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

Jingguo Bi,Qi Cheng,Maurice Rojas

Published 2012 in International Symposium on Symbolic and Algebraic Computation

ABSTRACT

We present a deterministic 2<sup><i>O(t)</i></sup><i>q</i><sup><i>t</i>-2/<i>t</i>-1 +<i>o</i>(1)</sup> algorithm to decide whether a univariate polynomial <i>f</i>, with exactly <i>t</i> monomial terms and degree <<i>q</i>, has a root in F<sub><i>q</i></sub>. Our method is the first with complexity <i>sub-linear</i> in <i>q</i> when <i>t</i>is fixed. We also prove a structural property for the nonzero roots in F<sub><i>q</i></sub> of any <i>t</i>-nomial: the nonzero roots always admit a partition into no more than 2√<i>t</i>-1(<i>q</i>-1)<sup><i>t</i>-2/<i>t</i>-1</sup> cosets of two subgroups <i>S</i><sub>1</sub> ⊆ <i>S</i><sub>2</sub> of F*<sub><i>q</i></sub>. This can be thought of as a finite field analogue of Descartes' Rule. A corollary of our results is the first deterministic sub-linear algorithm for detecting common degree one factors of <i>k</i>-tuples of <i>t</i>-nomials in F<sub><i>q</i></sub>[<i>x</i> when <i>k</i> and <i>t</i> are fixed. When <i>t</i> is not fixed we show that, for <i>p</i> prime, detecting roots in F<sub><i>p</i></sub> for <i>f</i> is NP-hard with respect to $BPP-reductions. Finally, we prove that if the complexity of root detection is sub-linear (in a refined sense), relative to the <i>straight-line program encoding</i>, then NEXP⊆P/poly.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-57 of 57 references · Page 1 of 1

CITED BY

Showing 1-18 of 18 citing papers · Page 1 of 1