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$.
 A: For $p>2$ prime, $-1$ is a quadratic residue modulo $p$ if and only if $p \equiv 1 \bmod 4$. So you can determine whether $-1$ is a quadratic residue modulo $p$ as quickly as you can find the remainder of $p$ upon division by $4$.
A: If $p = 2$ then $-1$ is a square mod $p$, so we may now assume that $p$ is odd. Suppose that $n^2 \equiv -1 \bmod p$ for some $n \in \mathbb{N}$. Then, using that $\mathbb{Z}/p\mathbb{Z}$ is a field,
$$
1 \equiv n^{p-1} \equiv (n^2)^{\frac{p-1}{2}} \equiv (-1)^{\frac{p - 1}{2}} \bmod p
$$
which implies that $\frac{p-1}{2}$ is even, thus, that $p \equiv 1 \bmod 4$. Conversely, suppose that $p \equiv 1 \bmod 4$. Then $\frac{p-1}{2}$ is even. Using that $\mathbb{Z}/p\mathbb{Z}$ is a field, pick a generator $x$ of $\mathbb{Z}/p\mathbb{Z}^\times$. $x^{\frac{p-1}{2}}$ is a root of $T^2 - 1$ different from $1$, such that
$$
-1 \equiv x^{\frac{p-1}{2}} \equiv (x^{\frac{p-1}{4}})^2.
$$
We have shown that $-1$ is a square mod $p$ if and only if $p \equiv 1 \bmod 4$ or $p = 2$.
As a sidenote, this observation can be generalised to $\mathbb{Z}/p^n\mathbb{Z}$ for a prime $p$, i.e. $-1$ is a square mod $p^n$ if and only if $p \equiv 1 \bmod 4$ (or $p = 2$ AND $n = 1$). Using the Chinese Remainder Theorem then, one can easily conclude that $-1$ is a square modulo $n$ if and only if $n$ is divisible by $2$ at most once and all odd primes $p$ dividing $n$ satisfy $p \equiv 1 \bmod 4$.
A: $\mathbb{Z}/p\mathbb{Z}$ is a field, so its multiplicative group is cyclic. In particular, if $p$ is an odd prime and if $g$ is any generator then $-1 = g^{(p-1)/2}$, which is a square root iff $(p-1)/2$ is even.
If $p=2$ then $-1 = 1 = 1^2$ so it holds rather trivially. 
A: 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.  
