An irreducible polynomial of degree 8 over a field $\mathbb{F}_p$ I need to find (for another excersize) a prime number $p$ and an irreducible polynomial of degree $8$ in $\mathbb{F}_p[x]$. Both I am free to choose.
My only worthwhile attempt was using the characterisation of irreducibility of cyclotomic polynomials over $\mathbb{F}_p$. That could have worked because $\Phi_{16}$ is of degree 8, but it turned out that no prime generates $\mathbb{Z}_{16}^*$, so it didn't.
Also, I've found this answer, but I find it quite unsatisfying.
As you can might tell, I know very few methods to prove irreducibility over a finite field, so I'd like to hear any of your ideas.
Note that you can choose both $p$ and the polynomial to be as convenient as you can.
Thank you!
 A: In order to generate irreducible polynomials quickly, we need some specific means of determining when we can go from $f(x)$ irreducible to $f(x^2)$ irreducible.
We first see what goes wrong in the most basic case we can consider.  The cyclotomic polynomial $\phi_4(x) = x^2+1$ is irreducible over $\Bbb F_p$ for all primes $p$ of form $4k+3$, but $\phi_8(x) = \phi_4(x^2) = x^4+1$ is not.  This follows from the fact that 8 divides $p^2-1$, so that $\Bbb F_{p^2}$ already contains eighth roots of unity (its multiplicative group being cyclic of order $p^2-1$).  Any element of $\Bbb F_{p^2}$ is quadratic over $\Bbb F_p$, so $x^4+1$ splits into quadratic terms over $\Bbb F_p$.
Note that since $p$ is odd, the quadratic field extension $\Bbb F_{p^4}/\Bbb F_{p^2}$ can be viewed as adjoining the square root of some element $\alpha \in \Bbb F_{p^2}$ (This requires the quadratic formula, which breaks down if $p = 2$).  If the minimal polynomial over $\Bbb F_p$ of $\alpha$ is given by the quadratic $f(x)$, then the square root $\sqrt{\alpha}$  satisfies $f(x^2)$.  Since $\Bbb F_p[\sqrt{\alpha}]= \Bbb F_{p^4}$, we must in fact have that $f(x^2)$ is the irreducible minimal polynomial for $\sqrt{\alpha}$.
So what went wrong in the case $f(x) = x^2+1$? It is the irreducible polynomial for $\zeta_4$  a primitive fourth roots of unity, and since $\Bbb F_{p^2}$ has eighth roots of unity it follows that $\zeta_4$ already has a square root in $\Bbb F_{p^2}$, and is thus not a valid choice for $\alpha$ above.  We need to find an appropriate quadratic whose roots do not have square roots in $\Bbb F_{p^2}$.  It will suffice to find a primitive $2^k$-th root of unity, where $2^k$ is the greatest power of 2 dividing $p^2-1$.
For concreteness sake set $p=3$.  Then we recall that $x^2+1$ has roots given by primitive 4th roots of unity, so the roots of $x^4+1 = (x^2+x+2)(x^2+2x+2)$ are primitive 8-th roots of unity.  This then implies by above that formally adjoining primitive 16-th roots of unity will give elements whose minimal polynomials are $x^4+x^2+2$ and $x^4 + 2x^2+2$.
We then note that 16 is the largest power of 2 dividing $3^4-1$, so the primitive 32nd roots of unity generate $\Bbb F_{3^8}$.  However, we similarly observe that the primitive 32nd roots of unity will satisfy $x^8+x^4+2$ and $x^8 + 2x^4+2$, which will therefore be irreducible over $\Bbb F_3$.
I think this method can be used to reasonably generate irreducibles of degree $2^k$ over $\Bbb F_{p}$ for $p$ odd.  Not sure if there's something reasonable for $p=2$, though.
A: Let $p$ be a prime congruent to $1$ modulo $8$. Let $a$ be a quadratic
nonresidue modulo $p$. Then $x^8-a$ is irreducible over $\Bbb F_p$.
One can replace $8$ by a power of a prime $l$ here, if we then take $a$
to be not an $l$-th power modulo $p$.
