You say that is a squarerootmod ? That is true all of the time. is the square root of , mod .

What you probably mean is that is asquaremod with probability 1/2. This is because there are as many nonzero squares as there are non-squares mod (when is odd).

To see that this is true, notice that the nonzero squares mod are precisely the roots of the polynomial , which has no repeated roots.