<p>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.</p>

<p>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.</p>

<p><a href="http://www.cs.umd.edu/~jkatz/THESES/sze.pdf" rel="nofollow">ON SOLVING UNIVARIATE POLYNOMIAL
EQUATIONS OVER FINITE FIELDS
AND SOME RELATED PROBLEMS</a>
Tsz Wo Sze, Doctor of Philosophy, 2007</p>

<blockquote>
  <p>...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.</p>
</blockquote>

CC BY-SA 3.0
2014-01-22T17:17:09.740Z
this "answer" should be a comment with a link to the thesis.
Sasho Nikolov
CC BY-SA 3.0
2014-01-22T17:28:19.537Z
@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
CC BY-SA 3.0
2014-01-22T17:44:35.100Z
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
CC BY-SA 3.0
2014-01-22T18:44:54.907Z
as stated am going on premise that a rough/nearby ref is better than no ref at all. afaict nobody else has given any refs either in the question or comments so far. apparently the general problem is, as the thesis focuses on, "univariate polynomial equations over finite fields". nobody has used that terminology yet in comments. from what I can tell it does indeed cover efficiently solvable special cases of "EPRP", right? its not a _general answer_ but shows someone attacking tractable instances of the problem which is usually closely related to more general cases.
vzn
CC BY-SA 3.0
2014-01-22T18:49:01.737Z
closer look at question. sorry! didnt notice the $r^x$ term. is $x$ integer? rational? what? geez
vzn
CC BY-SA 3.0
2014-01-22T19:03:09.957Z
how about this one? closer/warmer? [RATIONAL SOLUTIONS OF POLYNOMIAL-EXPONENTIAL EQUATIONS](http://ptmat.fc.ul.pt/~ayhan/rat_sol_poly_exp.pdf) GUNAYDIN. does not consider complexity but is basically sketching out algorithms. has an overview.
vzn
CC BY-SA 3.0
2014-01-22T20:38:41.707Z
@vzn, $x$ is obviously an integer, being an element of the finite field $GF(q)$ with $q$ being a prime. I am not interested to any special case. I just want to make sure that nobody proved that the problem is NP-complete (since the probability of it being in P is practically zero).
Massimo Cafaro
CC BY-SA 3.0
2014-01-22T20:48:50.017Z
interpreted the 1st sentence as literally the _coefficients_ are drawn from the finite field. ok, fine, $x$ is also. thx for clarification
vzn
CC BY-SA 3.0
2014-01-22T20:59:18.957Z
hmmm oops last ref not over fields. how about maybe [exponential sums over finite fields](http://www.math.ethz.ch/~kowalski/exp-sums.pdf) (kowalski), could it be recast into that maybe? suggest the basic problem name be determined 1st (clearly that alone is hard enough) & then worry about the complexity of it later as a 2ndary issue. the general eqn is surely studied in number theory somewhere... selecting an exponent _also_ from the field seems unusual in this area... it _is_ univariate in $x$ right? how many "primitive roots of the field" are there?
vzn
CC BY-SA 3.0
2014-01-23T15:03:29.063Z
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
CC BY-SA 3.0
2014-01-26T07:52:07.990Z
@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
CC BY-SA 3.0
2014-01-26T15:34:39.533Z
@massimo another angle, maybe the general field here seems to be called [exponential diophantine eqns](http://www.mathunion.org/ICM/ICM1978.1/Main/icm1978.1.0381.0388.ocr.pdf), survey by Tijdeman. basically agree with you that its probably not yet studied in complexity theory except for the special case noted above in comments, the discrete log (but which of course is high significance in cstheory)... it would help if you give some indication whether youve already done any literature search, it isnt that clear from earlier question phrasing/comments.
vzn
CC BY-SA 3.0
2014-01-26T15:43:41.053Z
here is a more recent ref 2011 but also by same author Tijdeman, [Exponential diophantine eqns](http://www.cambridge.org/us/academic/subjects/mathematics/number-theory/exponential-diophantine-equations?format=AR)... there are some solution methods given in these refs but presumably their complexity is not (yet) studied... with "beginners mind" dont see an immediate reason why there would be methods faster than the iterate-through-powers ones you sketch out in your question....
vzn
CC BY-SA 3.0
2014-01-22T17:09:05.173Z
2014-01-22T17:09:05.173Z
vzn
<p>I am trying to understand to which complexity class the following problem belongs:</p>

<p><strong>Exponentiating Polynomial Root Problem (EPRP)</strong></p>

<p>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$.</p>

<p>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.</p>

<p>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:</p>

<ul>
<li><p>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;</p></li>
<li><p>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 <em>identical</em> 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.</p></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2014-01-16T15:50:01.043Z
What do you mean with "proved NP-intermediate"?
Cornelius Brand
CC BY-SA 3.0
2014-01-16T15:57:02.677Z
Sorry, I meant is believed to be NP-intermediate. I am editing the question to reflect this.
Massimo Cafaro
CC BY-SA 3.0
2014-01-16T16:12:48.520Z
When you say "determine the roots of $p(x) = r^x$", do you mean to determine the roots of $p(x) - r^x$ (or determine the solutions to the equation $p(x) = r^x$ if you prefer to state it that way)?
D.W.
CC BY-SA 3.0
2014-01-16T16:20:23.950Z
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
CC BY-SA 3.0
2014-01-16T16:38:15.593Z
@MassimoCafaro, that was a little hint to edit the question to make it cleraer. :-)  I've done it for you.
D.W.
CC BY-SA 3.0
2014-01-19T21:38:06.113Z
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
CC BY-SA 3.0
2014-01-19T21:43:43.563Z
@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
CC BY-SA 3.0
2014-01-19T21:44:59.957Z
@domotorp, you are right, I missed that part. :) If there it is in BQP then one can take that as a reason that it is not NP-complete.
Kaveh
CC BY-SA 3.0
2014-01-21T19:16:20.790Z
Do I understand correctly that you're looking for roots over the field $GF(q)$?  How do you define $r^x$ when $x$ is an element of your field, are you working with a specific realization of the field (e.g. a specific primitive polynomial)?  Unlike the discrete logarithm problem (where canonically the domain is $x\in\mathbb{Z}$) this problem would seem to be dependent on very specific details of representation.
Steven Stadnicki
CC BY-SA 3.0
2014-01-21T19:31:01.270Z
@StevenStadnicki Yes, the problem is finding the roots over $GF(q)$ with q a prime number. Then, $r^x$ is simply exponentiating the primitive root $r$.
Massimo Cafaro
CC BY-SA 3.0
2014-01-21T19:32:48.897Z
@MassimoCafaro Ahhh, all right - that makes more sense; I'm used to $q$ standing for a prime _power_ in this context, so that $GF(q)$ is notation for $GF(p^n)$ (e.g., the perfectly good field $GF(2^{32})$).  If you specifically mean the finite fields of prime rather than prime-power size, I'd suggest making that explicit in the question?
Steven Stadnicki
CC BY-SA 3.0
2014-01-21T19:56:23.243Z
@StevenStadnicki I have edited my question accordingly. Thank you for the suggestion.
Massimo Cafaro
CC BY-SA 3.0
2014-01-22T11:40:28.310Z
crossposted: http://mathoverflow.net/questions/154721/efficient-algorithms-to-determine-the-roots-of-px-rx-in-the-finite-fiel
domotorp
CC BY-SA 3.0
2014-01-23T17:54:35.983Z
@MassimoCafaro we have a policy against simultaneous cross-posting,please avoid it in the future since it is disrespectful to the users of both sites and tends to split the discussion.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-23T18:17:53.647Z
@ArtemKaznatcheev I am sorry, I was not aware of this policy. The reason I cross-posted is simple: on TCS I was searching for an answer specifically related to computational complexity, while on MO I was searching for a math-oriented answer. The focus is indeed clear, looking at both post. Anyway, now I am fully aware of this policy and I will stick to it in the future. Thank you for informing me.
Massimo Cafaro
<cc.complexity-theory><reference-request><comp-number-theory><np-intermediate>
Complexity class of this problem?
Massimo Cafaro
# Complexity class of this problem?

(Asked by: username_0 on 2014-01-16)

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.

**Tags:** cc.complexity-theory, reference-request, comp-number-theory, np-intermediate
> **Comments:**
> **username_1**: What do you mean with "proved NP-intermediate"?  
> **username_0**: Sorry, I meant is believed to be NP-intermediate. I am editing the question to reflect this.  
> **username_2**: When you say "determine the roots of $p(x) = r^x$", do you mean to determine the roots of $p(x) - r^x$ (or determine the solutions to the equation $p(x) = r^x$ if you prefer to state it that way)?  
> **username_0**: 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.  
> **username_2**: @MassimoCafaro, that was a little hint to edit the question to make it cleraer. :-)  I've done it for you.  
> **username_3**: 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.  
> **username_4**: @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.  
> **username_3**: @domotorp, you are right, I missed that part. :) If there it is in BQP then one can take that as a reason that it is not NP-complete.  
> **username_5**: Do I understand correctly that you're looking for roots over the field $GF(q)$?  How do you define $r^x$ when $x$ is an element of your field, are you working with a specific realization of the field (e.g. a specific primitive polynomial)?  Unlike the discrete logarithm problem (where canonically the domain is $x\in\mathbb{Z}$) this problem would seem to be dependent on very specific details of representation.  
> **username_0**: @StevenStadnicki Yes, the problem is finding the roots over $GF(q)$ with q a prime number. Then, $r^x$ is simply exponentiating the primitive root $r$.  
> **username_5**: @MassimoCafaro Ahhh, all right - that makes more sense; I'm used to $q$ standing for a prime _power_ in this context, so that $GF(q)$ is notation for $GF(p^n)$ (e.g., the perfectly good field $GF(2^{32})$).  If you specifically mean the finite fields of prime rather than prime-power size, I'd suggest making that explicit in the question?  
> **username_0**: @StevenStadnicki I have edited my question accordingly. Thank you for the suggestion.  
> **username_4**: crossposted: http://mathoverflow.net/questions/154721/efficient-algorithms-to-determine-the-roots-of-px-rx-in-the-finite-fiel  
> **username_6**: @MassimoCafaro we have a policy against simultaneous cross-posting,please avoid it in the future since it is disrespectful to the users of both sites and tends to split the discussion.  
> **username_0**: @ArtemKaznatcheev I am sorry, I was not aware of this policy. The reason I cross-posted is simple: on TCS I was searching for an answer specifically related to computational complexity, while on MO I was searching for a math-oriented answer. The focus is indeed clear, looking at both post. Anyway, now I am fully aware of this policy and I will stick to it in the future. Thank you for informing me.  

---

## 1 answers

### Answer by username_7 on 2014-01-22. Score: -6

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](http://www.cs.umd.edu/~jkatz/THESES/sze.pdf)
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.

> **Comments:**
> **username_8**: this "answer" should be a comment with a link to the thesis.  
> **username_0**: @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.  
> **username_0**: 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 ;-)  
> **username_7**: as stated am going on premise that a rough/nearby ref is better than no ref at all. afaict nobody else has given any refs either in the question or comments so far. apparently the general problem is, as the thesis focuses on, "univariate polynomial equations over finite fields". nobody has used that terminology yet in comments. from what I can tell it does indeed cover efficiently solvable special cases of "EPRP", right? its not a _general answer_ but shows someone attacking tractable instances of the problem which is usually closely related to more general cases.  
> **username_7**: closer look at question. sorry! didnt notice the $r^x$ term. is $x$ integer? rational? what? geez  
> **username_7**: how about this one? closer/warmer? [RATIONAL SOLUTIONS OF POLYNOMIAL-EXPONENTIAL EQUATIONS](http://ptmat.fc.ul.pt/~ayhan/rat_sol_poly_exp.pdf) GUNAYDIN. does not consider complexity but is basically sketching out algorithms. has an overview.  
> **username_0**: @vzn, $x$ is obviously an integer, being an element of the finite field $GF(q)$ with $q$ being a prime. I am not interested to any special case. I just want to make sure that nobody proved that the problem is NP-complete (since the probability of it being in P is practically zero).  
> **username_7**: interpreted the 1st sentence as literally the _coefficients_ are drawn from the finite field. ok, fine, $x$ is also. thx for clarification  
> **username_7**: hmmm oops last ref not over fields. how about maybe [exponential sums over finite fields](http://www.math.ethz.ch/~kowalski/exp-sums.pdf) (kowalski), could it be recast into that maybe? suggest the basic problem name be determined 1st (clearly that alone is hard enough) & then worry about the complexity of it later as a 2ndary issue. the general eqn is surely studied in number theory somewhere... selecting an exponent _also_ from the field seems unusual in this area... it _is_ univariate in $x$ right? how many "primitive roots of the field" are there?  
> **username_0**: 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))$.  
> **username_9**: @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.  
> **username_7**: @massimo another angle, maybe the general field here seems to be called [exponential diophantine eqns](http://www.mathunion.org/ICM/ICM1978.1/Main/icm1978.1.0381.0388.ocr.pdf), survey by Tijdeman. basically agree with you that its probably not yet studied in complexity theory except for the special case noted above in comments, the discrete log (but which of course is high significance in cstheory)... it would help if you give some indication whether youve already done any literature search, it isnt that clear from earlier question phrasing/comments.  
> **username_7**: here is a more recent ref 2011 but also by same author Tijdeman, [Exponential diophantine eqns](http://www.cambridge.org/us/academic/subjects/mathematics/number-theory/exponential-diophantine-equations?format=AR)... there are some solution methods given in these refs but presumably their complexity is not (yet) studied... with "beginners mind" dont see an immediate reason why there would be methods faster than the iterate-through-powers ones you sketch out in your question....  

---

