Is there an efficient way to compute the square root of modulo prime? 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.

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}$$
