0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ There is the Modulus option in Solve however my experience is that it isn't perfect. $\endgroup$
    – Artes
    Commented Dec 20, 2013 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$
    – Massimo Cafaro
    Commented Dec 20, 2013 at 17:19

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
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$
    – Daniel Lichtblau
    Commented Dec 20, 2013 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$
    – Massimo Cafaro
    Commented Dec 21, 2013 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$
    – Massimo Cafaro
    Commented Dec 21, 2013 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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