# 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!

(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$.

• Just confirming, if I restrict $r$, you disbelieve there is a general way? Jul 31 '18 at 19:15

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$).

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.

• (-1) although this is true, it doesn't really answer the question and should be a comment. There isn't even a clear evidence that the OP wasn't aware of that. Jul 31 '18 at 23:24