Introduction to Cryptography with Coding Theory, 3rd Edition

3.10 Legendre and Jacobi Symbols

Suppose we want to determine whether or not $x^2\equiv a(\text{mod}p)$ has a solution, where $p$ is prime. If $p$ is small, we could square all of the numbers mod $p$ and see if $a$ is on the list. When $p$ is large, this is impractical. If $p\equiv 3(\text{mod}4)\text{,}$ we can use the technique of the previous section and compute $s\equiv a^{(p+1)/4}(\text{mod}p)\text{.}$ If $a$ has a square root, then $s$ is one of them, so we simply have to square $s$ and see if we get $a\text{.}$ If not, then $a$ has no square root mod $p\text{.}$ The following proposition gives a method for deciding whether $a$ is a square mod $p$ that works for arbitrary odd $p\text{.}$

Proposition

Let $p$ be an odd prime and let $a$ be an integer with $a\cancel{\equiv }0(\text{mod}p)\text{.}$ Then $a^{(p-1)/2}\equiv \pm 1(\text{mod}p)\text{.}$ The congruence $x^2\equiv a(\text{mod}p)$ has a solution if and only ...