2
$\begingroup$

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)

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I doubt that efficient algorithms are known -- for instance Bi, Cheng and Rojas recently published a proof that there is an algorithm running in time $p^{m^2+O(m)}$, which of course is very far from $\text{poly}(m)$. Their paper is arxiv.org/abs/1204.1113 $\endgroup$
    – Michael Zieve
    Aug 6, 2014 at 1:20

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.