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

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$
• Find a $k$ with $\left(\frac{k}{p}\right) = -1$. Then $k^{(p-1)/4}$ does the trick. The smallest quadratic nonresidue is typically small. Jul 31 '14 at 22:11
• You want the smallest, so yes, you take the modulus, and it could be that $p - (k^{(p-1)/4}\bmod p)$ is smaller, so we need a $\pm$. Jul 31 '14 at 22:22
• And, following up on @DanielFischer's comment, the most efficient way to find a quadratic non-residue is guess-and-check. Probabilistic, yes, but, ... :) Jul 31 '14 at 22:26
• en.wikipedia.org/wiki/Cipolla%27s_algorithm Jul 31 '14 at 22:30
• en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm Jul 31 '14 at 22:30

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}$.