2
$\begingroup$

I am trying to solve the well-known $g^x = y \pmod{N}$ but in this case only $g$ is unknown. What I know :

  • $x$ is a prime : $2^{16} + 1$
  • $y$ is known
  • $N$ is a large number that I managed to factor to two "less large" primes (like 38 figures each)

I found various methods to deal with discrete logarithm but it seems they are always intended to solve $x$. Maybe the answer is not that hard to find but this is a bit beyond my mathematical skill at this point :) Any help is appreciated.

$\endgroup$
  • 4
    $\begingroup$ You are actually trying to compute a modular root rather than a logarithm. $\endgroup$ – SEJPM May 12 '17 at 19:57
4
$\begingroup$

This is actually an RSA decryption problem, not a discrete log problem.

In this case, $$g = y^{x^{-1} \bmod \phi(N)} \pmod N$$

If you have the factorization $N = pq$, where $p, q$ are both prime, this is essentially:

$$g = y^{x^{-1} \bmod (p-1)(q-1)} \bmod N$$

You can compute $x^{-1} \bmod (p-1)(q-1)$ (or, what would work equally well, $x^{-1} \bmod \text{lcm}((p-1)(q-1))$), using the Extended Euclidean Algorithm for computing multiplicative inverses.

$\endgroup$
  • $\begingroup$ Thank you, it worked and your answer is very clear. I ended up using Euler's theorem to compute $x^{-1} \bmod (p-1)(q-1)$ since it is a bit more straighforward to me. The numbers were huge so I had to rewrite $g^x \pmod{N}$ so my computer wouldn't blow up. I share the python function for those who could be as clueless as me : link $\endgroup$ – chris May 13 '17 at 8:13
  • $\begingroup$ @chris : ​ docs.python.org/3.5/library/functions.html#pow ​ ​ ​ ​ $\endgroup$ – user991 May 13 '17 at 9:06
  • $\begingroup$ I wasn't aware of the optional modulo argument, thanks. $\endgroup$ – chris May 13 '17 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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