Quadratic Congruences with prime moduli
Let $a$ be a quadratic residue modulo $p$, i.e., the Legendre Symbol $(\frac{a}{p}) = 1$.
Then, the equation $$ x^2 \equiv a \pmod{p} \tag{1} $$ has exactly two solutions $x_0, p  x_0$.
How to find the two solutions?
Case 1: $p \equiv 3 \pmod{4}$
For this case, an explicit formula exists that can handle this easily: $$ x_0 \equiv a^{\frac{p + 1}{4}} \pmod{p} \tag{2} $$ Proof: $$ \begin{aligned} x_0^2 & \equiv a^{\frac{p + 1}{4}\cdot 2} \newline &\equiv a^{\frac{p + 1}{2}} \newline &\equiv a\cdot a^{\frac{p  1}{2}} \newline &\equiv a\cdot 1 \newline &\equiv a \pmod{p} \end{aligned} $$
For the last second $\equiv$, Euler’s criterion says that $a^{\frac{p1}{2}} \equiv (\frac{a}{p}) \pmod{p}$, and since here $a$ is a QR, thus $a^{\frac{p1}{2}} \equiv 1 \pmod{p}$.
Case 2: $p \equiv 1 \pmod{4}$
No trivial solution exists for this case, but several adhoc algorithms, one of which is TonelliShanks Algorithm, could solve this.
TonelliShanks Algorithm Implementation:
For more information, please refer to wiki .


Example
 $p=193$ and $a = 67$
 $p=569$ and $a = 367$
 $p=34369$ and $a = 19170$
 $p=50753$ and $a = 12957$
 $p=97241$ and $a = 47861$
 $p=2773676993$ and $a = 1342865413$


Computational Analysis
According to Wikipedia :
The Tonelli–Shanks algorithm requires (on average over all possible input (quadratic residues and quadratic nonresidues)) $$ 2m + 2k + \frac{S(S1)}{4} + \frac{1}{2^{S1}}  9 $$ modular multiplications, where $m$ is the number of digits in the binary representation of $p$ and $k$ is the number of ones in the binary representation of $p$.
Summary
From Solving quadratic congruences with odd prime moduli :
Overall, the TonelliShanks algorithm works efficiently in solving the quadratic congruence equation (1). Along with the explicit formula (2) that handles the case of odd prime congruent to 3 modulo 4, the quadratic congruence equations are completely and efficiently solved. As a result, it is not possible to hide secrets using quadratic congruence equations with odd prime moduli. If a message is embedded as a solution of such equation, then it can be easily recovered using the TonelliShanks algorithm or the explicit formula (2). On the other hand, the equation $$ x^2 \equiv a \pmod{n} \tag{3} $$ is difficult to solve where the modulus $n$ is the product of two large primes $p$ and $q$. In fact the Rabin cryptosystem is based on the difficulty of solving equation (3). However, if the factoring of $n$ is known, equation (3) is solvable and the TonelliShanks algorithm along with the Chinese remainder theorem play a crucial role.