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$?
- $p = 29, n = \pm 12$
- $p = 37, n = \pm 6$
- $p = 41, n = \pm 9$
- $p = 53, n = \pm 23$