# More efficient method of computing the square root of $-1 \mod p$

I am currently doing collecting some preliminary data about elliptic curves over finite fields of order $p$ where $p$ is a prime congruent to 1 mod 4. Part of the data collection process requires me to calculate the square root of $-1$ mod $p$, and I have been doing so by using the value $(\frac{p-1}{2})!$ reduced mod $p$. However calculating the factorial has required loops and hasn't been the most computationally efficient. Does any one know of a formula for the square root of $-1 \mod p$ that is easier to work with, at least from a computing perspective?

I downloaded Wagon's article, he suggests finding $c,$ the smallest quadratic non-residue $\pmod p,$ then your square root of $-1$ will be $$c^{(p-1)/4}$$

He gives an example with $p \equiv 5 \pmod 8,$ so that we immediately know we can take $c=2.$ For $p \equiv 1 \pmod 8,$ the search for a nonresidue will still not be very long.

The reason this is fast is that we can use the powermod algorithm. The version I implemented is https://en.wikipedia.org/wiki/Exponentiation_by_squaring

Here is their "Basic Method" with the prime included:

   demands n > 0

Function exp-by-squaring-iterative(x, n, p)
y := 1;
x := x % p;
while n > 1 do
if n is even then
x := x * x;
x := x % p;
n := n / 2;
else
y := x * y;
y := y % p;
x := x * x;
x := x % p;
n := (n – 1) / 2;
return (x * y) % p


https://en.wikipedia.org/wiki/Modular_exponentiation