13

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.

Massimo Cafaro
  • 2,216
  • 20
  • 19
  • What do you mean with "proved NP-intermediate"? – Cornelius Brand Jan 16 '14 at 15:50
  • 1
    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
  • 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. Jan 16 '14 at 16:12
  • 1
    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
  • @MassimoCafaro, that was a little hint to edit the question to make it cleraer. :-) I've done it for you. – D.W. Jan 16 '14 at 16:38
  • 1
    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
  • 2
    @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
  • @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 Jan 19 '14 at 21:44
  • 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 Jan 21 '14 at 19:16
  • @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 Jan 21 '14 at 19:31
  • @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 Jan 21 '14 at 19:32
  • @StevenStadnicki I have edited my question accordingly. Thank you for the suggestion. – Massimo Cafaro Jan 21 '14 at 19:56
  • 1
    crossposted: http://mathoverflow.net/questions/154721/efficient-algorithms-to-determine-the-roots-of-px-rx-in-the-finite-fiel – domotorp Jan 22 '14 at 11:40
  • @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 Jan 23 '14 at 17:54
  • @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 Jan 23 '14 at 18:17

1 Answers1

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

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 2
    this "answer" should be a comment with a link to the thesis. – Sasho Nikolov Jan 22 '14 at 17:17
  • 1
    @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
  • 1
    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
  • 1
    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 Jan 22 '14 at 18:44
  • 1
    closer look at question. sorry! didnt notice the $r^x$ term. is $x$ integer? rational? what? geez – vzn Jan 22 '14 at 18:49
  • 1
    how about this one? closer/warmer? RATIONAL SOLUTIONS OF POLYNOMIAL-EXPONENTIAL EQUATIONS GUNAYDIN. does not consider complexity but is basically sketching out algorithms. has an overview. – vzn Jan 22 '14 at 19:03
  • @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 Jan 22 '14 at 20:38
  • 1
    interpreted the 1st sentence as literally the coefficients are drawn from the finite field. ok, fine, $x$ is also. thx for clarification – vzn Jan 22 '14 at 20:48
  • 1
    hmmm oops last ref not over fields. how about maybe exponential sums over finite fields (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 Jan 22 '14 at 20:59
  • 2
    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
  • 3
    @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 07:52
  • @massimo another angle, maybe the general field here seems to be called exponential diophantine eqns, 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 Jan 26 '14 at 15:34
  • here is a more recent ref 2011 but also by same author Tijdeman, Exponential diophantine eqns... 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 Jan 26 '14 at 15:43