# How to enter and solve this equation in finite fields?

Is there a way in Mathematica 9 to enter and solve the following equation

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

EDIT

As an example, how to solve

$x^3 + x^5 == 3^x$ mod 7

-
There is the Modulus option in Solve however my experience is that it isn't perfect. – Artes Dec 20 '13 at 17:16
@Artes, thank you. I have edited my question adding an example equation I would like to solve. Forgive me, if my knowledge was better, I would not ask ;-) – Massimo Cafaro Dec 20 '13 at 17:19

The problem with the question is that exponential functions such as b^x are not well-defined functions modulo m, even when m is prime. In general, when the base b is relatively prime to m, the period of b^x divides EulerPhi[m].

The same problem of defining b^x holds when b and x belong to a field of order λ^n. I only know of the exponential being defined for x an integer, which induces a function on the integers modulo λ-1 in the case of a finite field of characteristic λ.

Example:

λ = 71;
Pick[Range[λ], Mod[x^3 + x^5 - 3^x, λ] /. {x -> Range[λ]}, 0]
Pick[Range[λ], Mod[x^3 + x^5 - 3^x, λ] /. {x -> 3 λ + Range[λ]}, 0]

(* {54} *)
(* {34} *)


Conclusion: If x is to be an element of a finite field, then the equation is undefined.

If, however, x is merely to be chosen from the set of integers {1, .., λ}, then the following will work.

λ = 71; (* changing the prime from 7 to 71 *)
Pick[Range[λ], Table[Mod[x^3 + x^5 - 3^x, λ], {x, λ}], 0]

(* {54} *)


If x is to be chosen from the set {0, .., λ-1}, then use the following instead.

Pick[Range[0, λ-1], Table[Mod[x^3 + x^5 - 3^x, λ], {x, 0, λ-1}], 0]


But it only makes a difference (for this example equation) for λ = 3.

-
I doubt there is anything significantly better than brute search (like this). Solve can handle such problems over R due to a sophisticated extension of polynomial rootfinding. Over finite fields I'm not aware of any such capability. – Daniel Lichtblau Dec 20 '13 at 19:47
If the finite field $\mathbb{F}$ has a small number of elements, one 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}$ because we are working on a finite field. The problem is reduced to finding the roots of the polynomial $g = p - f \in \mathbb{F}[x]$. A brute-force approach, trying every element in the field would work. Another possibility would be to factor $g$ using Berlekamp's or Cantor–Zassenhaus's algorithms and read the roots off the factors. – Massimo Cafaro Dec 21 '13 at 7:51
However, both exhaustive search and the Berlekamp's and Cantor–Zassenhaus's algorithms require exponential time. I need to be sure that no polynomial time algorithm exists in order to apply this to the construction of a cryptographic protocol. – Massimo Cafaro Dec 21 '13 at 7:53