# Construction of Irreducible Polynomials over Finite Fields

I understand construction of irreducible polynomials over finite fields is a non trivial problem. Can anyone please refer me to good resources regarding constructive approaches of irreducible polynomials?

Also a perspective of how construction of irreducible polynomial will help to understand other branches of mathematics such as coding theory, cryptography,etc., will be very helpful.

I am currently reading Lidl's 'Finite Fields' and found the conditions regarding the same problem a bit absurd looking and not very intuitive, (specially chapher 3, section 3 part). Can I have better ways to comprehend those results?

Added by mixedmath
The OP indicated in the comments that the parts of this book that are relevant are theorems 3.36 and 3.37. For ease, I display what is freely available here. Unfortunately, there is no theorem 3.36. But there is an example 3.36: And the part of the theorem that we can access:    The rest is not included in the preview.

Edit:

I found this http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf , in this paper the authors give an algorithm for constructing irreducible polynomials, but my mathematical background does not permit me to understand the paper fully, still if someone please explains the steps in the first algorithm with an example i will be glad.

Specifically the fourth step of the first algorithm remains unclear to me.

• You cannot assume that everyone has a copy of your book at hand. What are the absurd unintuitive conditions in Lidl's book? – Phira May 28 '12 at 7:49
• If you are refering to Lidl & Niederreiter, then I would say that it is the good resource. I know of relatively few families of irreducible polynomials, and most (if not all?) are listed in that book. Either buried in the theory, or as exercises. I understand you in the sense that that section may disappoint you at the first reading. You would hope someting better to be there, but no better recipes are known. – Jyrki Lahtonen May 28 '12 at 10:45
• @jyrki latonen, thanks for the suggestion. But can you please elaborate on the thought process behind those results, specifically, if some one is not aware of the results before hand then how will he/she be inspired to think on those conditions and the techniques? – Aranya Lahiri May 28 '12 at 16:34
• For the purposes of constructing fields of characteristic two (useful in many an application in your list) I use the primitive (hence irreducible) polynomials listed here. – Jyrki Lahtonen May 28 '12 at 16:34
• @Phira unfortunately i can't copy the theorems and they are so long i can't reproduce them, will you be kind enough to check books.google.co.in/… , theorem 3.36 and theorem 3.37? sorry for the inconvenience – Aranya Lahiri May 28 '12 at 16:35

## 3 Answers

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.

• thanks a lot, now i seem to understand things a bit more clearly. – Aranya Lahiri May 30 '12 at 18:56

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.

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.