# 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!

• For proving irreducibility you can just try to divide the potential irreducible polynomial by all irreducible polynomials of lower degree (in your case up to degree 4). For $\mathcal{F}_2[x]$ you can try this $1+x+x^3+x^4+x^8$ (if I'm not wrong). – Ben373 Jun 16 '17 at 23:12
• well, in $\mathbb F_2[x]$ you only have $2^{7}$ choices. Even less when you notice the sum of coefficients must be odd – Jorge Fernández Hidalgo Jun 16 '17 at 23:13

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$.

• Let me see if I got it right: the condition $p\equiv_8 1$ assures that all $8$ths roots of unity are in $\mathbb{F}_8$. Now we can use Kummer's theorem about cyclic extenstions to say that $[\mathbb{F}_p(\sqrt[8]{a}):\mathbb{F}_p]$ equals the minimal $\ell$ such that $(\sqrt[8]{a})^{\ell}\in$ $\mathbb{F}_p$. And this is $8$ because $a$ is a quadratic nonresidue. Are these the right considerations? – 35T41 Jun 17 '17 at 8:13
• @35T41 Exactly! – Angina Seng Jun 17 '17 at 12:30

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.

• Wow, some very nice arguments. Thanks! – 35T41 Jun 17 '17 at 7:01