Para empezar, considere el siguiente candidato de la factorización:
$$
(x^2+ax-1)(x^2+bx-1)=x^4+(a+b)x^3+(ab-2)x^2-(a+b)x+1.
$$
Esto funciona si $a+b\equiv 12$$ab\equiv 16$. El discriminante de la ecuación cuadrática
$$
(T-a)(T-b)=T^2-(a+b)T+ab=T^2-12T+16
$$
es igual a $20$. Así que si $20$ es un residuo cuadrático módulo $p$, entonces tenemos una factorización
de este tipo. Como $20=2^2\cdot5$ que realmente nos interesa, si $5$ es un residuo cuadrático módulo $p$ o no. Por la reciprocidad cuadrática esto sucede, iff $p$ es un residuo cuadrático módulo $5$. Así tenemos que la factorización de este tipo existe, iff $p\equiv\pm1\pmod5.$ Del curso, esto es equivalente a $p$ siendo congruentes a $1,9,11$ o $19$ modulo $20$.
No sé, si es fácil o difícil extender este elemental argumento y detectar, si estos factores cuadráticos se divide aún más. Además, este argumento, obviamente, no se descarta la posibilidad de que otros factores cuadráticos, pero parecía tener el casos $p\equiv\pm2\pmod 5$ cubierto ya.