Given $x' \in \{-x, x\} \bmod q$ (where $q$ could be any prime of my choice), $s$ is a random element in the field, $y = x'\cdot s$ and $y' = \pm\sqrt{(x\cdot s)^2}\bmod q$ (i.e., both solutions to the quadratic residue), is there a way to tell whether $x'= x\bmod q$ or $x' = -x \bmod q$?

If not, is there some other known result about quadratic residues I can utilize, assuming I can choose $q$ to be whatever prime (or composite) I'd like and can compute multiple QRs of the form $y_i = (x\cdot s_i)^2 \bmod q$?

  • $\begingroup$ There are no signs in finite fields and so one cannot distinguish between $x$ and $-x$ without some context relating it some other field element. For example, $3$ is a primitive element (call it $\alpha$) in GF$(7)$ and so we can distinguish between $2 =\alpha^2$ and $-2 = 5 = \alpha^5$, but given just $\{2, 5\}$, we cannot say $x$ is $\alpha^2$ and $-x$ is $\alpha^5$ for some unspecified $\alpha$. After all, $\beta = 5$ is also a primitive element and the set $\{2,5\}$ could be $\{\beta,\beta^4\}$ instead. $\endgroup$ Mar 20 '16 at 14:28
  • $\begingroup$ One can certainly distinguish between $x$ and $-x$, except in characteristic $2$ where they are equal. $\endgroup$
    – fkraiem
    Mar 20 '16 at 16:08
  • 1
    $\begingroup$ @fkraiem OK, in GF(7), which of the two elements $5$ and $2$ has a negative sign, and which has a positive sign? $\endgroup$ Mar 20 '16 at 21:31

Your Answer

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

Browse other questions tagged or ask your own question.