# Division by $2$ or principal root with DH oracle

Assume $$g$$ is generator of multiplicative group modulo prime $$p=2q+1$$ where $$q$$ is prime.

Assume we know $$g^{2t}\bmod p$$ and $$g^{2}\bmod p$$ and assume we can have access to a Diffie-Hellman oracle.

Can we find $$g^t\bmod p$$ in polynomial time?

Note if we can do that we can break discrete log with access to a DH oracle when generator order is even.

Can we find $$g^t \bmod p$$ in polynomial time?
We can find either $$g^t$$ or $$-g^{t} = g^{t + (p-1)/2}$$; obviously, we can't tell which one was the correct one with the information we were given.
Because $$p \equiv 3 \pmod 4$$ (because $$(p-1)/2$$ is assumed to be prime, and taking $$p=5$$ off the table - that can be handled as a special case), then [1] we can compute modular square-roots with the simple computation $$\sqrt{x} = \pm x^{(p+1)/4}$$.
So, we have $$g^t \in\{ -(g^{2t})^{(p+1)/4},+(g^{2t})^{(p+1)/4}\}$$, easily doable in polytime.
[1]: If $$p \equiv 1 \bmod 4$$, then it is still practical to compute modular squareroots, it's a bit more involved.
• @Turbo: no, it can't, because both values are possible solutions for $g^t$ Mar 27 at 19:31