Complexity class of this problem?

I am trying to understand to which complexity class the following problem belongs:

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$ a prime number, and $r$ a primitive root for that field. Determine the solutions of: $$p(x) = r^x$$ (or equivalently, the zeros of $p(x) - r^x$) where $r^x$ means exponentiating $r$.

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). 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 is believed to be NP-intermediate as well or belonging to any other complexity class ? A reference will be greatly appreciated. Thanks.

• Sorry, I meant is believed to be NP-intermediate. I am editing the question to reflect this. – Massimo Cafaro Jan 16 '14 at 15:57
• I prefer "determining the solutions to the equation $p(x)=r^x$", but, of course, determining the roots of $p(x) -r^x$" or, even better the roots of $p(x) - f(x)$" where $f(x)$ is the polynomial found by Lagrange interpolation as discussed in the question should be equivalent. – Massimo Cafaro Jan 16 '14 at 16:20
• Isn't discrete logarithm a special case of this? So it is at least as hard as discrete root and obviously in NP. If you believe discrete log is NPI then this one is also. You may want to ask if there is any efficient quantum algorithm for the problem. – Kaveh Jan 19 '14 at 21:38
• @Kaveh: It is mentioned in the question that discrete log is a special case. This problem could be harder (NP-complete), though I would guess they are the same. But you are right that searching for polynomial algorithms is quite hopeless. – domotorp Jan 19 '14 at 21:43
• crossposted: mathoverflow.net/questions/154721/… – domotorp Jan 22 '14 at 11:40

will take a stab at answering this. there are no refs given in the question but it is given an acronym "EPRP" as if more than one person has studied it. does anyone know if that is the case? the questioner MC seems to have significant bkg in this area but it would help significantly to list some "nearby" refs known/reviewed to understand why they have some gap that doesnt (?) cover this supposedly special case.

it usually helps to find "nearest available refs" and determine how the problem is different or similar. here is a comprehensive ref that seems to consider closely related problem(s). think that the questioner MC should try to locate the nearest case of the problem in this ref, or maybe some other one, and then point out how this case asked about is specifically different than general problem cases given in the ref. the ref has a long list of related refs to also check for nearby/related problem(s). he considers the complexity of the problem and gives efficient P-time algorithms for various cases.

ON SOLVING UNIVARIATE POLYNOMIAL EQUATIONS OVER FINITE FIELDS AND SOME RELATED PROBLEMS Tsz Wo Sze, Doctor of Philosophy, 2007

...we present a deterministic polynomial-time algorithm to solve polynomial equations over some families of finite fields. Note that polynomial equations are powerful constructs. Many problems can be formulated as polynomial equations.

• this "answer" should be a comment with a link to the thesis. – Sasho Nikolov Jan 22 '14 at 17:17
• @vzn, the main algorithms (berlekamp, Cantor-Zassenhaus and Lagrange interpolation) have been cited in my question and you can easily find tons of related materials searching the web. I could even add the Shoup algorithm here, but I am not able to add any single reference in which this problem has been investigated. The acronym "EPRP" is just a way to refer to the problem, you will not find it in the literature. Anyway, I have checked the reference you kindly provided, but the problems studied are way too easy and based on simplifying assumptions that, unfortunately, do not apply in my case. – Massimo Cafaro Jan 22 '14 at 17:28
• Also, the problems studied in the Ph.D. thesis are not "general": they are specific problems, with simplifying assumptions that make them tractable. Very interesting and solid work, but, if Dr. Tsz Wo Sze had solved EPRP with a polynomial time algorithm, he would have been probably awarded the Fields medal by now ;-) – Massimo Cafaro Jan 22 '14 at 17:44
• The reference you provided does not help unfortunately. I checked everything I had access to, but no luck. It looks like this problem has not been investigated. This is why I am asking about: I need to make sure that either no results are available or, if even a single result has been published, I need to know about. The polynomial is univariate in $x$. Finally, the number of primitive roots is exactly $\phi(\phi(q))$. – Massimo Cafaro Jan 23 '14 at 15:03
• @VZN: hey dude, why do you continually troll this site? It's getting to be a joke. You are obviously a computer science wannabe ( you don't even use your real identity like the other real scientists here like Shor and Growchow, ect. – William Hird Jan 26 '14 at 7:52