I'm modifying the Diffie Hellman protocol as follows: We are given a large prime number $p$ and exponent $x$ such that $0 \lt x \lt p-1$ and $\mathrm{gcd}(x, p-1) = 1$. Also we pick $g$ such as $1 \lt g \lt p-1$.

We are also given $y = (g^x) \bmod{p}$. Essentially, we know about the prime $p$, the exponent $x$ and the result $y$. But $g$ is kept secret.

This is similar to Diffie Hellman protocol except that exponent $x$ is made public while $g$ is kept secret. So I'm trying to find if there's an efficient way to determine the secret $g$ or is this also a discrete logarithm problem?

  • 1
    $\begingroup$ Yes, it's easy to recover $g$. If you assure me that this is not homework, I'll tell you how... $\endgroup$
    – poncho
    Apr 3, 2018 at 17:10
  • $\begingroup$ No this isn't related to any homework $\endgroup$ Apr 4, 2018 at 0:20

1 Answer 1


Yes, there's an easy way to recover $g$:

$$g = y^{x^{-1} \bmod p-1} \bmod p$$

This works because the multiplicative group $\mathbb{Z}_p^*$ has order $p-1$, and hence $g = g^{x \cdot x^{-1}} = (g^x)^{x^{-1}} = y^{x^{-1}}$

  • $\begingroup$ I see. Why didn't I see that before. This clarifies my doubt. So in this case it means that the problem is simple and is not a discrete logarithm problem (unlike the original diffie hellman). I'm accepting your answer. $\endgroup$ Apr 4, 2018 at 3:25

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.