# Diffie Helman obtaining $g^y \bmod p$ from $g^{xy} \bmod p$ and $g^x \bmod p$

This may seem like a strange question. Lets say I have $$g^x \bmod p$$ and $$g^{xy} \bmod p$$. How can I efficiently obtain $$g^y \bmod p$$? I assume I must use modular inverse but I don't know where.

Lets say I have $$g^x \bmod p$$ and $$g^{xy} \bmod p$$. How can I efficiently obtain $$g^y \bmod p$$?

We hope that there is no efficient method (without using knowledge of $$x$$ or $$y$$)

Here's why: if you can solve that problem, you can solve the (computational) Diffie-Hellman problem; here's how:

• Suppose that you did have an Oracle that, given $$g, g^x, g^{xy}$$, returned $$g^y$$

• Then, you can use that to create an Oracle that, given $$h, h^x$$, returned $$h^{x^{-1}}$$

Here's how, you'd call your Oracle with $$g=h, g^x=h^x$$ and $$g^{xy} = h$$. These conditions hold only if $$x^{-1} = y$$, and so when your Oracle returns $$g^y$$, that's also $$h^{x^{-1}}$$

• With that Oracle, you can generate a squaring Oracle (given $$h, h^x$$, return $$h^{x^2}$$, and with that, computing DH is straight-forward.

• @mathman123123: I don't see how those modifications would change my answer; with the Oracle, it would still be able to compute unmodified DH, so unless you're in a group where DH was weak, it looks impossible Apr 17, 2021 at 12:35