4
$\begingroup$

An encryption scheme is based on the DLP: $c = a^x mod ~b$, where $x$ is hard to find. How hard is it to find $a$, given all the other values, $c$, $x$ and $b$?

Would this make the problem easy to solve?

$c^{1/x} = (a^x)^{1/x} mod ~b$

An example would be great to better understand.

$\endgroup$
1
  • $\begingroup$ $c^{x^{-1}\pmod {\phi(b)}}=a \pmod b$ $\endgroup$ Mar 17, 2017 at 18:07

1 Answer 1

3
$\begingroup$

If you know the factorization of $b$, it's easy. One way would be to compute $x^{-1}$, the multiplicative inverse modulo $\phi(b)$, and then compute $c^{x^{-1}} \bmod b$

If you don't know the factorization of $b$, it's hard; in fact, it's essentially the RSA problem.

$\endgroup$
2
  • 1
    $\begingroup$ why would i need to compute the multiplicative inverse modulo if it wont be used in the computation $c^{x^{-1}} mod ~b$ ? $\endgroup$
    – user123
    Mar 17, 2017 at 18:12
  • $\begingroup$ @user123: $c^{x^{-1}} \bmod b$ is meant as a sorthand for$$c^{(x^{-1}\bmod\phi(b)\;)} \bmod b$$ and thus makes use of $x^{-1}\bmod\phi(b)$, the multiplicative inverse of $x$ modulo $\phi(b)$. $\endgroup$
    – fgrieu
    Mar 17, 2017 at 18:27

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.