How to find $x^2 \equiv -1 \pmod{p}$? By Euler Criterion, it is true that if $p \equiv 1 \pmod{4}$ then there exists a integer $x$ such that $x^2 \equiv -1 \pmod{p}$.
But how do I find $x$?
 A: Probably the easiest algorithmic approach is to try to find a primitive root of $p$, although actually a primitive root as such is a stronger requirement than is needed. Note that I'm assuming $p$ is prime.
Choose candidate numbers $a_i$ - generally it is better if $a_i$ and $p{-}a_i$ are non-squares. Then use modular exponentiation to find $a_i^s \bmod p$ where $s$ is the largest odd factor of $p{-}1$ - that is, $p-1=s\cdot 2^d$. If this is equivalent to $1$ or $-1(\equiv p-1)$, you need to pick another candidate. Otherwise you can square this until you get $-1$. Then the number at the previous step is a square root of $-1$. 
This works because $\phi(p-1)$ of the numbers less than $p$ will be primitive roots, so they should be relatively easy to find, and the looser constraint here mean that even more number may be able to provide a suitable path to finding your required $x$.
A: Suppose $p \equiv 1 \mod{4}$ with $p$ being prime. Then there is an integer $n$ such that $p = 4n + 1$. Let $a = (2n)!$. We have
\begin{align}
a^2
&\equiv (\prod_{j = 1}^{2n} j)(\prod_{j = 1}^{2n} -j) \mod{p}\\
&\equiv \prod_{j = 1}^{2n} j(-j) \mod{p}\\
&\equiv \prod_{j = 1}^{2n}j(p - j) \mod{p}\\
&\equiv \prod_{j = 1}^{2n}j(4n + 1 - j) \mod{p}\\
&\equiv (\prod_{j = 1}^{2n} j)( \prod_{j = 2n + 1}^{4n} j) \mod{p}\\
&\equiv (4n)! \mod{p}\\
&\equiv (p - 1)! \mod{p}
\end{align}
and by Wilson's Theorem $(p - 1)! \equiv - 1 \mod{p}$ so we have $a^2 \equiv - 1 \mod{p}$. Thus $a$ is such an integer.
