5
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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

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

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ (-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. $\endgroup$ Jul 31 '18 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.