A fast algorithm for finding square root modulo p

We propose a novel algorithm for finding square roots modulo prime . Taking Square root modulo prime of 3(mod 4) type is known to be straightforward. However, for odd primes of 1(mod 4) type , finding square root remains non-trivial. Tonelli-Shanks algorithm remains the most widely used and probably the fastest when averaged over all primes. This paper proposes a novel approach for finding square roots modulo odd primes, which turns out to be much faster than existing Tonelli-Shanks algorithms. Apart from faster computation time, the proposed method does not require availability of non-residue and can work with 'relative non-residue' also. The relative non-residues are much easier to find ( probability 2/3) compared to non-residues ( probability 1/2).