# Discrete logarithm with unknown base

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.

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

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.

• 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 – chris May 13 '17 at 8:13
• @chris : ​ docs.python.org/3.5/library/functions.html#pow ​ ​ ​ ​ – user991 May 13 '17 at 9:06
• I wasn't aware of the optional modulo argument, thanks. – chris May 13 '17 at 10:20