He estado tratando de llegar a una primaria de la construcción, pero fue en vano. Son más avanzadas herramientas necesarias?
Si consideramos un analógica a esta pregunta en la que no se requieren p primo (es decir, si hay infinitamente muchos enteros $n$ tal que $n^2+1$ es divisible por un primo mayor que $n$), entonces la pregunta se convierte en mucho más fácil:
Escoge un prime $p$ $1$ mod $4$, y deje $g$ ser un generador de mod $p$. A continuación, la elección de $n\equiv g^{\frac{p-1}{4}}$ mod $p$,$n<p$, funciona.