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

Question

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?

Answer 1

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