Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients drawn from a finite field $GF(q)$ with $q$ prime, and $r$ a primitive root for that field. Determine the solutions of:
$$p(x) = r^x $$
where $x\in\{0,\dots,q-1\}$.
Note that, when $\deg(p)=0$ (the polynomial is a constant), this problem reverts to the Discrete Logarithm Problem, which is believed to be NP-Intermediate, i.e. it is in NP but neither in P nor NP-complete.
To the best of my knowledge, efficient (polynomial) algorithms to solve this problem  do not exist (Berlekamp and Cantor–Zassenhaus algorithms require exponential time to solve this particular problem, see below). Finding roots to such equation can be done in two ways:


*

*Try all possible items $x$ in the field, and check whether they
satisfy the equation or not. Clearly, this requires exponential time in the bitsize of the field
modulus;

*The exponential $r^x$ can be rewritten in polynomial form, by using
Lagrange interpolation to interpolate the points
$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$, determining a
polynomial $f(x)$. This polynomial is identical to $r^{x}$ precisely because we are working on a finite field. Then, the difference $p(x) - f(x)$, can be
factored in order to find the roots of the given equation (using
Berlekamp or Cantor–Zassenhaus algorithms) and the roots read off the factors. However, this approach is
even worse than exhaustive search: since, on average, a polynomial
passing by $n$ given points will have $n$ non-null coefficients, even
only the input to Lagrange interpolation will require exponential
space in the field bit size.
Does anyone know if this problem can be solved efficiently by using a different approach and algorithms ? A reference will be greatly appreciated. Thanks.
 A: This question is not posed well. Let $F={\mathbb F}_q$ where $q$ is a prime-power.
A polynomial $f\in F[x]$ gives rise to a function $\phi(f)\colon F\to F$ via evaluation. Moreover, 
$\phi\colon F[x]\to F^F\colon f\mapsto\phi(f)$ is an epimorphism onto the ring $F^F$ of all functions $F\to F$. Indeed, $F[x]/(x^q-x)\cong F^F$. Thus your exponential function $p(x)=r^x$ is equivalent to a polynomial function $f(x)$ of degree at most $q-1$. [Edit: Using Noam Elkies comment below, $\deg(f)$ is exactly $q-1$.] It seems to me that you should just replace the function $p(x)$ with the equivalent polynomial $f(x)$, and considering the difference
$p(x)-f(x)$ is unhelpful.
Factoring a degree $n$ polynomial over ${\mathbb F}_q$ using the Cantor-Zassenhaus algorithm has complexity ${\rm O}^{\sim}(n^2\log q)$. Since $n=\deg(f)= q-1$, factorization algorithms will not give you a polynomial in the input size $\log q$.
A: For an argument of why this probably doesn't have an easy solution, note that for every value $a$ such that $p(a) \neq 0$, the discrete log problem and the Chinese remainder theorem together show there exists a unique $b \in \{ 0, 1, 2, \ldots, q(q-1) - 1 \}$ such that $b \equiv a \pmod{q}$ and $p(b) = r^b$.
So the problem isn't "does this have any roots", but "does this have any small roots", which is pretty hard to deal with.
