Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields
Résumé
We present a deterministic 2O(t)qt-2/t-1 +o(1) algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree