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!
 A: (I'm assuming $p$ is odd)
No; the answer to your question depends crucially on what you have chosen for $r$. 
In your example you took $r = 46$ so that $y=56$ was the right answer, but you could just as easily have taken $r = 99$ instead, which would make $y=51$ the right answer. You could also have chosen $r=152$, but that gives the same result as $r=46$.
If you want to do something like restrict $r$ to the range $0 < r < \frac{p}{2}$, I strongly disbelieve there is a general way to distinguish which of the two square you're asking for without basically computing $r$.
A: If $y^2 \equiv (g^r)^2 \pmod p$ then $y \equiv \pm g^r \pmod p$, because $\Bbb Z/p\Bbb Z$ is a field.
A: 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$).
