Construction of Irreducible Polynomials over Finite Fields

Solution 1:

The main explanation of the fourth step of the first algorithm in the link you gave is given in the proof. In order to construct an extension of degree $p^a n$, you first construct an extension $\def\FF{\mathbb{F}}\FF(\beta)/\FF$ of degree $n$, another extension $\FF(\alpha_a)/\FF$ of degree $p^a$, and then the field $\FF(\alpha_a, \beta)/\FF$ has to be degree $p^a n$.

A common trick to find generators for a field extension with multiple generators is to take linear combinations. By looking at the action of the Galois group, it's easy to see that $\alpha_a + \beta$ has full order. Use your favorite method to find its minimal polynomial.

To construct the extension of degree $p^a$, they constructed it in stages, with extensions $\FF(\alpha_k)/\FF$ of degree $p^k$. Artin-Schreier theory says that (in characteristic $p$), any Galois extension of degree $p$ (all finite finite field extensions are Galois) can be written as the splitting field of $x^p - x - r$ for some $r$. Lemma 5 gives a way to find suitable $r$.

For the record, I don't follow exactly what their formulas are doing either. But by knowing what they're trying to do, IMO it's easy enough to come up with your own way to do it.

Solution 2:

Adding an explanation as to how I see Example 3.36. Hopefully this adds to your intuition.

The known fact that the polynomials $p_1(x)=x^4+x^3+1$ and $p_2(x)=x^4+x+1$ are primitive (i.e. have roots of maximal order, here $2^{\deg p}-1=15$) is the starting point. Consider a polynomial $q_i(x)=p_i(x^5), i=1,2.$ Let $\beta$ be one of its roots. Then $p(\beta^5)=0$, so $\beta^5$ is of order $15$. Because $5$ is a factor of $15$ this already implies that the order of $\beta$ is $5\cdot15=75$. But we don't know yet that $q_i$ would be irreducible. We can deduce this as follows.

Remember that the degree of the minimal polynomial (over a the prime field $\mathbb{F}_2$) of a root of unity of (odd) order $\ell$ is the smallest integer $r$ such that $\ell\mid 2^r-1$. This is because that is the smallest $r$ such that $\mathbb{F}_2^*$ has a cyclic subgroup of order $\ell$. Note that this is equivalent to saying that $$ r=\mathrm{ord}_{\mathbb{Z}_\ell^*}(2) $$ is the (multiplicative) order of the coset of $2$ modulo $\ell$. Here $2^r\equiv1\pmod{75}$, iff $2^r\equiv1\pmod{15}$ and $2^r\equiv1\pmod{25}$. The latter congruence is of interest here. That's because we know that $\mathbb{Z}_{25}^*$ is cyclic of order $\phi(25)=20.$ We know (or easily verify) that $2$ is of order 4 in $\mathbb{Z}_5^*$, but that $2^4\not\equiv1\pmod{5^2}$. Therefore $r=\mathrm{ord}_{\mathbb{Z}_{25}^*}(2)$ is a proper multiple of 4, but must also be a factor of $4\cdot5$. As 5 is a prime, we conclude that $r=20$. Hence the minimal polynomial of $\beta$ has degree $20$, and thus must be $q_i(x)$.

The preceding results, Lemma 3.34 and Theorem 3.35, describe this more generally. But my point is that this is also a manifestation of the familiar result from elementary number theory: if the order of an integer $g$ modulo a prime power $p^a$ is $r$, then the order of $g$ modulo $p^{a+1}$ is either $r$ or $pr$.

Note that if the order of the root of $p$ is $\ell$, and we define a new, hopefully irreducible, polynomial by declaring $q(x)=p(x^s)$, where $s$ is a prime, then it is absolutely essential that $s\mid \ell$. If we use a prime $s$ that is not a factor of $\ell$, then things won't work (think Chinese remainder theorem, Little Fermat and all that jazz). As an example consider $f(x)=p_1(x^{17})=x^{68}+x^{17}+1.$ If $\beta$ is a root of $f$, then $\beta^{17}$ is a root of $p_1$, and hence of order 15. Therefore already at this point we get options: the order of $\beta$ may be either $15$ or $15\cdot17=255$. Here both possibilities will occur. If $\alpha$ is a root of $p_1$, then $\alpha^{17}=\alpha^{16}\cdot\alpha=\alpha^2$ is a conjugate of $\alpha$, so we see that $p_1(x)\mid f(x)$. The remaining roots of $f$ are of order 255, but as the order of 2 modulo 255 is eight, this gives us a bunch of factors of degree 8 for $f(x)$. At this point it is not difficult to see that $f(x)$ has a single quartic factor $p_1(x)$ and eight distinct irreducible factors of degree 8.

Solution 3:

Just to add another alternative to construct the list of irreducible polynomials using a bruteforce approach: you can simply try every possible polynomial between 2^p and 2^p * 2 and then just test their primality. This is described here with sourcecode here.