Solving quadratic congruences? I am having trouble learning to solve quadratic congruences.  I need to solve $$
x^2=317\pmod{ 77747}
$$ 
using two different methods.  Setting up in an index table isn't feasible since $p$ is so high. It's easy enough to determine it is solvable because 
$$
a^{38873}=1 \pmod{77747}.
$$
I have no idea where to proceed from here though.  Any help would be greatly appreciated. 
 A: You have already calculated :
$$317^{38873}=1 \text{ mod }77747 $$
Now $38873=1+2\times 19436$. Hence :
$$317\times (317^{19436})^2=1  \text{ mod }77747$$
$$317= (317^{-19436})^2 \text{ mod }77747$$
Now $317^{-1}=-14225$ (using a Bezout algorithm). So :
$$317=( (-14225)^{19436})^2\text{ mod }77747$$
By some computer calculation (dichotomic exponentiation mod $77747$) :
$$(-14225)^{19436}=30622\text{ mod }77747$$
Well now you can check that indeed $30622^2=937706884=317$ mod $77747$.
A: Let $p = 77747,\,$ then $ p \equiv 3 \pmod 4$ and you can compute a square root $x$
as a power of $317:$
$$x \equiv 317^{(p+1)/4}  \equiv 317^{19437} \equiv 30622 \pmod p .$$
The last value can be evaluated with a fast binary powering algorithm. A second root is $y\equiv -x \equiv 47125 \pmod p$. You can easily verify that $x^2\equiv  y^2 \equiv 317 \pmod p$.
The result $x \equiv a^{(p+1)/4} \pmod p$ to compute a square root of $a$ for $p \equiv 3 \pmod 4$ was found by Lagrange, see Wiki.
A second, more general method to compute modular square roots is the Tonelli–Shanks algorithm, which works for all primes $p.$
