3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Ben373 Jun 16 '17 at 23:12
  • $\begingroup$ well, in $\mathbb F_2[x]$ you only have $2^{7}$ choices. Even less when you notice the sum of coefficients must be odd $\endgroup$ – Jorge Fernández Hidalgo Jun 16 '17 at 23:13
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – 35T41 Jun 17 '17 at 8:13
  • 1
    $\begingroup$ @35T41 Exactly! $\endgroup$ – Angina Seng Jun 17 '17 at 12:30
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.