Is there an efficient way to compute the square root of modulo prime?

Question

Is there a reasonably simple way to find the square root of $a$ modulo $p$ where $p$ is an odd prime? If the odd prime is small number it seems you can do this by brute force. HOwever if we want to solve something like x^2=2 mod 103 (whose solution is 38 and 65 mod 103) is pretty cumbersome because we have a non-linear Diophantine equation x^2=2+101y. Is there an efficient and quick method to solve something of this kind? If I try primitive roots then the first primitive root is 5 not 2 so that does not help.

Answer 1

Let $p$ be an odd prime and we can say whether an integer $a$, $a\ne0(\mbox{mod})p,$ has a square root mod $p$ or not by $$\mbox{a is }\begin{cases}\mbox{a quadratic residue if $a^{\frac{p-1}{2}}\equiv 1(\mbox{mod }p)$} \\\mbox{a quadratic nonresidue if $a^{\frac{p-1}{2}}\equiv -1(\mbox{mod }p)$}\end{cases}$$

Answer 2

Partial answer:

If $p=4n-1$, then let $b = a^{\frac{p+1}{4}}$. Then $b^2=a^\frac{p+1}{2}=a^{\frac{p-1}{2}}a\equiv a$ because of Euler's criterion.