Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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
up vote 3 down vote accepted

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.

share|improve this answer
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

Your Answer


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.