I know that the final result will be when $p \equiv 3 \mod 8$ or when $p\equiv 1 \mod 8$. However, I do not know what to do.
For the case of $X^2 + 1$, the solution is obvious since this is just when $F_p^{\times}$ has an element of order 4, and this is when $4|p-1$. All we know here is that 2 has a 4th root.
I'm guessing the procedure is straight forward, but it remains to elude me.