Find $\sqrt 7 \pmod {2579}$ Find $\sqrt 7 \pmod {2579}$.
I think I understand how I would solve a very basic equation like this:
$x^2 = 1 \pmod 5$
make a table of all the possible solutions like this
$x=0 \implies x^2=0 \\
x=1 \implies x^2=1 \\
x=2 \implies x^2=4 \\
x=3 \implies x^2=4 \\
x=4 \implies x^2=1 \\
x=5 \implies x^2=0$
then take the ones that work. In this case $\pm 1$ and $\pm 4$ are the roots, but how do I do this with a huge prime that I can't list out all the possibilities for? 

First, check that there are solutions for $x^2 \equiv 7 \bmod 2579 $ using Euler's criterion:

If $p$ is a prime that does not divide $a$,
  then
  $\qquad x^2 \equiv a \bmod p$ has a solution
  $\iff a^{\tfrac{p-1}{2}} \equiv 1 \bmod p$.

We compute and see that $7^{\frac{2579-1}{2}} \equiv 1 \bmod 2579$.
Next, we find the solutions using a theorem of Lagrange, which is easily checked:

If $p \equiv 3 \bmod 4$ and $a$ is a quadratic residue mod $p$, then
  $\qquad$ the solutions of $x^2 \equiv a \bmod p$ are $x \equiv  \pm a^{\frac{p+1}{4}} \bmod p$.

This theorem applies because $2579 \equiv 3 \bmod 4$ and $7$ is a quadratic residue mod $2579$, as above.
So, we compute $7^{645} \equiv 88 \bmod 2579$ and so the solutions are $\pm 88 \bmod 2579$.
