Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

1 Answer

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

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.

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

Your Answer

 
discard

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.