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 ?


As an example, how to solve

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

  • 1
    $\begingroup$ There is the Modulus option in Solve however my experience is that it isn't perfect. $\endgroup$
    – Artes
    Dec 20 '13 at 17:16
  • $\begingroup$ @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 ;-) $\endgroup$ 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 λ.


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

  • 3
    $\begingroup$ 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. $\endgroup$ Dec 20 '13 at 19:47
  • $\begingroup$ 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. $\endgroup$ Dec 21 '13 at 7:51
  • $\begingroup$ 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. $\endgroup$ Dec 21 '13 at 7:53

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.