1
$\begingroup$

If i have the following equation:

$$m^b = z^b \pmod{n}$$

Where all numbers are taken from the multiplicative group $\mathbb{Z}_n^*$.

Suppose I know the values $z$ and $b$. Can I state that $z = m$, or at least that it is a possible solution?

Is it the only solution?

$\endgroup$
  • $\begingroup$ $n$ is composite? take $b=2, m=2, z=-2$ $\endgroup$ – kelalaka Feb 9 at 19:48
  • 1
    $\begingroup$ @kelalaka but z=2, m=2 will also be correct so i can return z=m=2 as a possible answer, right ? $\endgroup$ – caffein Feb 9 at 19:54
  • $\begingroup$ @kelalaka Is it possible to find all possible solutions for such an equation ? (in general form) $\endgroup$ – caffein Feb 9 at 19:57
  • $\begingroup$ You should re-write your question for asking the general from. $\endgroup$ – kelalaka Feb 9 at 20:04
3
$\begingroup$

Is it the only solution?

It will be iff $b$ and $\phi(n)$ are relatively prime.

If $b$ is relatively prime to $\phi(n)$, then the operation $x \rightarrow x^b \bmod n$ is a permutation of the set $\mathbb{Z}_n^*$, hence there will be exactly one solution to the equation $m^b \equiv z^b \pmod n$ (and since we know that $m \equiv z$ must be a solution, it must be the only one.

If $b$ is not relatively prime to $\phi(n)$, then there must be a nontrivial solution to $c^b \equiv 1 \pmod n$ (where nontrivial means "other than 1"); in fact, there will be at least $\gcd(b, \phi(n))-1$ such nontrivial solutions. Values $m = z \cdot c^k \bmod n$ will be the other solutions to the equation.

As for finding these other solutions (which, as above, is equivalent to the problem of finding the nontrivial roots of 1), it's straight-forward if you know the factorization of $n$ (which is equivalent to knowing the value of $\phi(n)$; this includes the case of $n$ being prime.

First, we set $d = \gcd(b, \phi(n))$ and $e = b / d$ (and so $b = d \cdot e$, with $d$ being a factor of $\phi(n)$, and $e$ being relatively prime to $\phi(n)$.

Then, select a random value $r \in \mathbb{Z}_n^*$ and compute $s = r^{\phi(n)/d} \bmod n $; if $s$ happens to be 1, then go back and try another random number.

If $s \neq 1$, then set $c = s^{e^{-1} \bmod {\phi(n)}}$; that's one value of $c$

Now, if $d$ happens to be composite, then you might need to go through this procedure multiple times to find all the possible values of $c$; if $d$ is prime, then one value is sufficient (and the other roots of 1 are $c^k$ for $k \in \{2, …, d-1\}$

On the other hand, if you don't know the factorization of $n$, this is sometimes a hard problem, and sometimes not. A case where this is not a hard problem; $b = 2$, which has $c = n-1$ as an easy-to-find solution.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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