I need an efficient way to calculate the square root of a large number modulo a huge prime p, i.e. a way to calculate x^2 = q mod p, where q and p are given. q is in my case 13 digits and p 16 digits, which makes it practically impossible to bruteforce (in reasonable time).

I can't find anything helpful anywhere except tests whether it is a quadratic residue or not, and special cases... The tests seem to take as long as simply trying to bruteforce by testing if q, q+p, q+2p, q+3p, ..., are square roots. And my prime isn't on the form 4k+3 nor 8k+5 (which allegedly would mean that calculating the square root would be easy).

I would be very grateful for any help at all.