How quickly can we detect if $\sqrt{(-1)}$ exists modulo a prime $p$? How quickly can we detect if $\sqrt{(-1)}$ exists modulo a prime $p$?  In other words, how quickly can we determine if a natural, $n$ exists where $n^2 \equiv -1 \bmod p$?
NOTE
This $n$ is essentially the imaginary unit modulo $p$.

Let's do some experimentation. 
$p = 3$: no.
$p = 5$: yes, $2^2 \equiv -1$.
$p = 7$: no.
$p = 11$: no.
$p = 13$: yes, $5^2 \equiv -1$.
$p = 17$: yes, $4^2 \equiv -1$.
$p = 19$: no.
$p = 23$: no.
It appears that only those prime numbers which are congruent to $1$ modulo $4$ have this property.  
