Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
Actually what is $x$ in your problem ? Your sentence "Try all possible items x in the field" makes it look like you are thinking about $x\in\mathbb{F}_q$ but then $r^x$ does not make sense. –  Aurel Jan 16 at 21:17
1  
What is your definition of $r^x$ when $x$ is in $\mathbb{F}_q$ and $r$ is a primitive root in $\mathbb{F}_q$ ? –  Aurel Jan 17 at 7:39
1  
@MassimoCafaro: Do you assume $q$ to be prime and identify the elements of $\mathbb{F}_q$ with the integers $0, 1, \dots, q-1$? –  j.p. Jan 17 at 11:07
1  
@j.p.: yes, $q$ is prime and the elements of $GF(q)$ are the integers $0,1,…,q−1$ –  Massimo Cafaro Jan 17 at 13:38
3  
@MassimoCafaro: There is a Galois field with $q$ elements for each $q$ that is a power of a prime, so it was not clear. When you write "a finite field $GF(q)$" with no more precision, most people will think that $q$ can be a nontrivial power of a prime. And when you write $r^x$ with no more precision, most people will think you mean something satisfying $r^{x+y}=r^xr^y$. –  Aurel Jan 20 at 8:52

1 Answer 1

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

share|improve this answer
    
But the input size is $O(\log q)$, not $O(q)$. Exhaustion over the $q$ possible $x$ already gives an $\tilde O(q)$ algorithm, so $O(q^2 \log q)$ doesn't help. –  Noam D. Elkies Jan 25 at 14:13
    
@Noam There are $\phi(q-1)$ choices for the primitive element $r$. Could it be that the smallest value of $\deg(f)$, as $r$ varies, is ${\rm O}(\log q)$? –  Glasby Jan 25 at 14:23
2  
Sorry, it can't even be smaller than $q-1$: the polynomial $f(x+1)-rf(x)$ has degree $\deg \, f$ and and $q-1$ roots (all $x \neq -1$). –  Noam D. Elkies Jan 25 at 14:27
    
A good point. Thank you! –  Glasby Jan 25 at 14:31
    
@Glasby, why the primitive roots are only $\phi(q)$ instead of $\phi(\phi(q))$ ? –  Massimo Cafaro Jan 25 at 19:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.