number theory - Distinguishing between the square roots of a quadratic residue

For a prime $p$, given $g$, $x = g^{2r}\pmod p$, and $y$ such that $y^2 \equiv x \pmod p$, is it possible to determine if $y \equiv g^r \pmod p$ without calculating the discrete logarithm? Comparing numbers by size doesn't seem to help.

For example, with $p = 107$, $g = 2$, and $x = 2^{92} \equiv 33 \pmod {107}$, the square roots are $56$ and $51 \mod p$. Is there a way to determine that $56 \equiv 2^{46}$ just from the values of $p,g,x$ without computing/knowing r?

EDIT: Could this be possible if r is restricted to some range? like $0\leq r < \frac p2$ or $\frac p2 \leq r < p$? Thanks!

Answer

No. Suppose that you can find "true" (with respect to $g$) square root in $T(p)$ time (denote "true" square root of $x$ as $f_g (x)$). Then you can find discrete logarithm (for simplicity, let it take values $1, 2, \ldots, p - 1$ instead of usual choice $0, 1, \ldots, p - 2$) of any non-zero remainder modulo $p$ in $O(T(p) \mathrm{poly}(\log p))$ time:

$\log_g x = \begin{cases} 1 &\mbox{ if $x = g$ } \\ 2 \log_g f_g(x) &\mbox{ if $x$ is a quadratic residue} \\ 2 \log_g f_g(gx) - 1 &\mbox{ if $x$ is a quadratic non-residue and is not equal to $g$} \end{cases}$.

Notice that $\log_g f_g (x) = \dfrac{\log_g x}{2}$ and $\log_g f_g(gx) = \dfrac{\log_g x + 1}{2}$, so computation of $\log_g x$ using this recursive formula halts in $O(\log p)$ iterations. Also, making each recursive call takes
$O(\mathrm{poly}(\log p))$ time.

(Checking whether number is quadratic residue or not can be easily done in $O(\mathrm{poly}(\log p))$ time, for example one may calculate $x^{(p-1)/2} \!\!\! \mod \! p$ and check whether it is $1$ or $-1$).