Finding an $n$ such that $n^2 \equiv -1 \mod p$

Question

What is an efficient algorithm to find the first number $n$ such that $n^2 \equiv -1 \mod p$ for a prime $p$, if such an $n$ exists?

Is there anything better than the brute-force approach up to $p-1 \over 2$?

I know this is simple to find for primes of the form $n^2+1$ because $n^2 \equiv -1 \mod (n^2+1)$, resulting in $n$, but is there a fast way for a generic case $n$?

Ex:

• $p = 29, n = \pm 12$
• $p = 37, n = \pm 6$
• $p = 41, n = \pm 9$
• $p = 53, n = \pm 23$

Answer 1

Such an $n$ exists iff $p=1 \mod 4$. And also $p=1 \mod 4$ iff $p=x^2+y^2$ for integers $x, y$. Then the solution is $n=\frac{x}{y} \mod p$. This could be faster using $1\le x\le \sqrt{p}$.