I started to read about Diffie-Hellman exchange and I encountered a problem which I don't know how to solve.

Given $g=3$, $p=131$, $g^x\bmod p=112$, $g^y\bmod p=74$, compute $g^{xy}\bmod p$

  1. $113$
  2. $110$
  3. $112$
  4. $111$

How could I compute $g^{xy} \bmod p$? Or at least verify which one is correct. Any idea?


1 Answer 1


Actually, given $p,g,g^x\bmod p,g^y\bmod p$ deciding whether a given number is actually $g^{xy}\bmod p$ is also known as the Decisional Diffie-Hellman Problem (DDH), which sits at the basis of the (formal) security for the ElGamal cryptosystem and is assumed to be hard for properly chosen values of $p,g$ and $x,y$ in general.

For your particular scenario the best solution is to "just" solve the discrete logarithm problem, ie computing $x$ or $y$ and then computing $g^{xy}\bmod p$ to see which number falls out (113).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.