Explicit factorization of \(x^{2^ k}+1\) over \(F_ p\) with prime \(p\equiv 3\bmod 4\) (Q2366272)

The authors present a direct way to compute the coefficients of the irreducible factors of \(x^{2^ k}+1\) (\(k\geq 1\)) over \(F_ p\) for a prime \(p\equiv 3\bmod 4\). This problem is equivalent to the construction of the minimal polynomials of primitive \(2^{k+1}\)-th roots of unity over \(F_ p\) (which may be useful in applying the FFT) and to the construction of an irreducible polynomial of degree \(2^ e\). From the coefficients of the irreducible factors, one can produce quadratic residues and quadratic nonresidues in \(F_ p\).