# if $x^2 \bmod p = q$ and I know $p$ and $q$, how to get $x$?

if $x^2 \bmod p = q$ and I know $p$ and $q$, how to get $x$?

I'm aware this has to do with quadratic residues but I do not know how to actually solve it. $p$ is a prime of form $4k+3$

-
Bit of notation. Do you mean $x^2 \equiv q \pmod{p}$ –  user2468 Jul 15 '12 at 20:02
Please make the body of the question self-contained. The title is an indexing feature, much like writing the title of a book on the spine to make finding the book on the bookshelf easier. But you don't expect the book to start at the spine. –  Arturo Magidin Jul 15 '12 at 20:03
@J.D. $a\bmod b$ usually means the nonnegative remainder of $a$ when divided by $b$. It is the mathematical notation for the operation that many computer languages denote by % –  Arturo Magidin Jul 15 '12 at 20:04
There are reasonably efficient algorithms to compute square roots mod $\rm\,p,\:$ e.g. the Tonelli-Shanks and Cipolla algorithms. –  Bill Dubuque Jul 15 '12 at 20:04
There are algorithms for finding square roots when the modulus is prime. E.g.,, the Tonelli-Shanks algorithm. Finding square roots with composite moduli is computationally equivalent to factoring. –  Arturo Magidin Jul 15 '12 at 20:08

Euler's theorem says that $\left(\frac{q}{p}\right) \equiv q^{\frac{p-1}{2}} \bmod p$. On the other hand, assuming there is a solution, $\left(\frac{q}{p}\right) = 1$.

So you have $q^{\frac{p+1}{2}} \equiv q*q^{\frac{p-1}{2}} \equiv q \bmod p$. Since $p+1$ is divisible by $4$, this gives solutions $$x \equiv \pm q^{\frac{p+1}{4}} \bmod p.$$

-
hmm this doesn't seem to synthesize the answer I currently have but the equation works for one of the solutions –  MyNameIsKhan Jul 15 '12 at 20:24
@AgainstASicilian: No, no, no! That's not what people are telling you. You don't change the sign of $q$. once you know one value of $x$ that gives a solution, then $p-x$ is the other solution. There's no cleverness about it: it's exactly the same observation as noting that if $a$ is a solution to $x^2=b$ in the real numbers, then $-a$ is the other solution. –  Arturo Magidin Jul 15 '12 at 20:34
@AgainstASicilian The minus sign is outside of the exponent! –  Cocopuffs Jul 15 '12 at 20:35
@AgainstASicilian $(-1)^{100}$ is not the same as $-1^{100}$. –  Erick Wong Jul 15 '12 at 20:35
@AgainstASicilian: Because $-2912856368\bmod p = 1087143639$. –  Arturo Magidin Jul 15 '12 at 20:38

A finite field of order $\rm\:4n\!+\!3\:$ has subgroup of squares of order $\rm\:2n\!+\!1.\:$ But one easily shows that in any group of odd order $\rm\; 2n\!+\!1\:$ the equation $\rm\; x^2 = a\;$ has solution $\rm\: a^{n+1}\;$ (Lagrange, 1769).

More generally, there are reasonably efficient algorithms to compute square roots mod $\rm\,p,\:$ e.g. the Tonelli-Shanks and Cipolla algorithms.

-