Para cada impar prime $p$ tenemos $8\mid p^2-1$. El grupo multiplicativo del campo finito $F=GF(p^2)$ es cíclico de orden $p^2-1$. Poniendo estos dos bits juntos nos dice que hay una raíz primitiva $u$ orden $8$$F$. Debemos tener $u^4=-1$, debido a $-1$ es el único elemento de la multiplicativo de orden dos. Debido a $F$ es una ecuación cuadrática de la extensión de $\mathbf{Z}/p\mathbf{Z}$, el polinomio mínimo de a $u$ es de grado $\le 2$. Que el polinomio mínimo es entonces un factor de
$$x^4+1=(x-u)(x-u^3)(x-u^5)(x-u^7)=(x-u)(x-u^3)(x+u)(x+u^3).$$
====================
Edit: he Aquí una idea para encontrar la factorización. Me separé de ella en los casos de acuerdo a la clase de residuo de $p$ modulo 8. Supongamos primero que $p\equiv 1\pmod 4$ (o $p$ equivalente a $1$ o $5$ modulo 8). En ese caso, todo lo que necesitamos es una raíz cuadrada $i$ $-1$ modulo $p$. Si mal no recuerdo existe un algoritmo para la búsqueda de dos enteros $x,y$ tal que $p=x^2+y^2$, y, a continuación, $i=x*y^{-1}$ deseada es la raíz cuadrada en el primer campo de $F_p=GF(p)$. La factorización es entonces
$$
x^4+1=(x^2+i)(x^2-i).
$$
Observar que si $p\equiv1\pmod8$, en tanto cuadrática factores se divide aún más.
Si $p\equiv 3\pmod 8$, $u$ no está en el primer campo, y su conjugado es $u^p=u^3$. Por lo tanto, el polinomio mínimo es
$$
m(x)=(x-u)(x-u^p)=(x-u)(x-u^3)=x^2-[u+u^3]x + u^4= x^2-ax-1,
$$
donde $a$ es un desconocido elemento del primer campo. Debido a $u^5=-u$$u^7=-u^3$, el otro factor de $x^4+1$ debe $m(-x)=x^2+ax-1$. Tenemos que encontrar el coeficiente de $a$.
Vamos a multiplicar
$$
(x^2-ax-1)(x^2+ax-1)=(x^2-1)^2-a^2x^2=x^4-(2+a^2)x^2+1.
$$
Vemos que hemos encontrado la factorización, si podemos encontrar la $a=\sqrt{-2}$. Es bien sabido que cuando se $p\equiv 3\pmod 8$, $-2$ es un residuo cuadrático módulo $p$ que confirma nuestra conclusión.
En el último caso $p\equiv 7\pmod8$ el polinomio mínimo de a $u$ $F_p$ es
$$
m(x)=(x-u)(x-u^p)=(x-u)(x-u^7)=x^2-[u+u^7]x+u^8=x^2-bx+1
$$
para algunos $b\in F_p$. De nuevo el otro factor es $m(-x)$, similar al cálculo de la muestra que necesitamos $b=\sqrt{2}$. De nuevo esto encaja con el hecho conocido de que en este caso $2$ es un residuo cuadrático módulo $p$.
==================
Editar(2): TonyK descrito los siguientes métodos para encontrar las raíces cuadradas. Ellos dependen del hecho de que si $p$ es una extraña prime, y $gcd(a,p)=1$,$a^{(p-1)/2}\equiv\pm1\pmod p$. Aquí tenemos el signo más, si y sólo si $a$ es un residuo cuadrático (=QR) modulo $p$.
Si $p\equiv 3\pmod8$, entonces sabemos que $2$ no es un QR modulo $p$. Por lo tanto
$2^{(p-1)/2}\equiv -1\pmod p$. Por lo tanto $2^{(p+1)/2}\equiv -2\pmod p$. Pero aquí $(p+1)/2$ es un entero par, así que la escritura $z=2^{(p+1)/4}$ obtenemos $z^2\equiv 2^{(p+1)/2}\equiv -2$, y hemos encontrado una raíz cuadrada de $-2$.
Del mismo modo, si $p\equiv 7\pmod 8$, sabemos que $2$ es un residuo cuadrático módulo $p$. Esta vez $2^{(p+1)/2}\equiv 2$, y el mismo cálculo muestra que $z=2^{(p+1)/4}$ es una raíz cuadrada de $2$$F_p$.
Si $p\equiv 5\pmod 8$, luego de nuevo a $2$ no es un QR modulo $p$, lo $2^{(p-1)/2}\equiv -1\pmod p$ $(p-1)/2$ es incluso. Por lo tanto $z=2^{(p-1)/4}$ es una raíz cuadrada de $-1$. Si $p\equiv 1\pmod 8$, entonces no podemos usar $2$ (pero puede usar cualquier no-QR en su lugar, o el método mencionado anteriormente).
