  We propose a novel algorithm for finding square roots modulo p. Although
there exists a direct formula to calculate square root of an element modulo
prime (3 mod 4), but calculating square root modulo prime (1 mod 4) is non
trivial. Tonelli-Shanks algorithm remains the most widely used and probably the
fastest when averaged over all primes [19]. This paper proposes a new algorithm
for finding square roots modulo all odd primes, which shows improvement over
existing method in practical terms although asymptotically gives the same run
time as Tonelli-Shanks. Apart from practically efficient computation time, the
proposed method does not necessarily require availability of non-residue and
can work with `relative non-residue' also. Such `relative non-residues' are
much easier to find ( probability 2/3) compared to non-residues ( probability
1/2).
