I want to solve the following question:

Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to know whether there are roots of $f(x)$ in $F_p$.

I know this question can be quite easy if $e_m$ is small enough, since we just need to calculate $GCD(f(x),x^p-x)$, but here this process may take exponential time of $m$, which is not efficient.

So, does anyone knows whether there are efficient algorithms(i.e. runs in $poly(m)$) to solve this problem?(or to show it is NP-hard?)

(This question also been asked at here)

I want to solve the following question:

Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to know whether there are roots of $f(x)$ in $F_p$.

I know this question can be quite easy if $e_m$ is small enough, since we just need to calculate $GCD(f(x),x^p-x)$, but here this process may take exponential time of $m$, which is not efficient.

So, does anyone knows whether there are efficient algorithms(i.e. runs in $poly(m)$) to solve this problem?(or to show it is NP-hard?)

(This question also been asked at here)