2
$\begingroup$

Is there any analytical (exact, closed-form solution) or numerical method to solve an equation such as

$p(x) = r^x$

where $p(x)$ is a polynomial whose coefficients are drawn from a finite field, and $r$ is a primitive root of the field modulus ?

Or, is this problem known to be equivalent to solving the discrete logarithm problem ? Thank you in advance.

$\endgroup$
2
$\begingroup$

If the finite field $\mathbb{F}$ has a number of elements that is small enough, you can obtain the Lagrange interpolation polynomial $f \in \mathbb{F}[x]$ such that $f(x_i) = r^{x_i}$ for all elements $x_i \in \mathbb{F}$. This polynomial is identical to $r^{x}$ precisely because we are working on a finite field. Then, the problem is reduced to finding the roots of the polynomial $g = p - f \in \mathbb{F}[x]$. A brute-force approach consisting of trying every possible element in the field would work. Another possibility would be to factor $g$ using Berlekamp's algorithm and read the roots off the factors.

You can find further details on these types of algorithms (such as computational complexity, etc) in the computer algebra literature (see, for instance, this and this).

$\endgroup$
  • $\begingroup$ Thank you. But then, how much difficult is finding the roots of p(x) - f(x) ? Since we are not working in the continuous but in a finite field, what methods can be used and what is their complexity ? $\endgroup$ – Massimo Cafaro Dec 20 '13 at 16:44
  • $\begingroup$ I have edited my answer to address your questions. $\endgroup$ – Juan M. Bello-Rivas Dec 20 '13 at 17:19
  • 1
    $\begingroup$ Juan, thank you very much for the references. Exhaustive search, Berlekamp and Cantor–Zassenhaus algorithms require exponential time, exactly what I was hoping for since I want to apply this in the construction of a cryptographic protocol. $\endgroup$ – Massimo Cafaro Dec 21 '13 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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