[Math] Construction of Irreducible Polynomials over Finite Fields

finite-fieldspolynomials

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.

Best Answer

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.

Related Solutions

[Math] Characterization of irreducible polynomials over finite fields

Trying to say something more. I don't know, if this is at all what you were hoping.

Let us agree to look at monic polynomials only. Things like the following are known. If you specify any low degree part $a_dx^d+\cdots a_1x+a_0$ with a non-zero constant term, then asymptotically (for degree $n$ much higher than $d$) the residue classes of irreducible polynomials of degree $n$ modulo $x^{d+1}$ are uniformly distributed. In other words, each such low degree part appears equally often at the tail of an irreducible polynomial (well, the distribution is not exactly uniform for any specific $n$, but asymptotically the error term becomes negligible).

This result is obviously an analogue of Dirichlet's result of equidistribution of rational primes into (coprime) residue classes modulo $m$. Its proof is IMHO a bit simpler. See, e.g. Rosen's book.

Does this kill some of your hopes?

Families of known irreducible polynomials are few. The first one that comes to mind is the family of cyclotomic polynomials with zeros that are primitive roots of unity of an order that is a power of three. These polynomials $$ \phi_{3^\ell}(x)=x^{2\cdot3^{\ell-1}}+x^{3^{\ell-1}}+1 $$ remain irreducible over the field of two elements. The proof is an exercise in Lidl & Niederreiter, and is essentially equivalent to showing that two is a primitive root modulo $3^\ell$. This family of irreducible polynomials is admittedly very sparse.

Irreducible Polynomials over Finite Prime Fields

Tables are not so good to work with, one has to copy+paste. A mathematically good way to use computer algebra support for this task is sage. Here are some code snippets that answer the one or the other related aspect.

sage: F = GF(5)
sage: R.<x> = PolynomialRing(F)
sage: F
Finite Field of size 5
sage: R
Univariate Polynomial Ring in x over Finite Field of size 5
sage: R.irreducible_element?
sage: R.irreducible_element(12)
x^12 + x^7 + x^6 + 4*x^4 + 4*x^3 + 3*x^2 + 2*x + 2
sage: # The above is a possible choice of an irreductible polynomial.
sage: minimal_polynomials = list( set( [ f.minpoly() for f in GF(5**6) ] ) )
sage: minimal_polynomials = [ p for p in minimal_polynomials if p.degree() == 6 ] 
sage: minimal_polynomials . sort()
sage: len( minimal_polynomials )
2580
sage: for p in minimal_polynomials[:10]:
....:     print p
....:     
x^6 + x + 2
x^6 + 2*x + 3
x^6 + 3*x + 3
x^6 + 4*x + 2
x^6 + x^2 + x + 1
x^6 + x^2 + x + 3
x^6 + x^2 + 2*x + 2
x^6 + x^2 + 2*x + 4
x^6 + x^2 + 3*x + 2
x^6 + x^2 + 3*x + 4
sage: # These are the first ten minimal polynomials of some elements in GF(5**6), after sorting them

sage: # Alternatively, we can factor the polynomial extracted from the Frobenius isomorphism
sage: F = GF(2)
sage: K.<a> = GF(2**9)
sage: R.<x> = PolynomialRing(F)
sage: myfactors = [ f for f, multiplicity in (x^(2^9)-x).factor() if f.degree() == 9 ]
sage: len(myfactors)
56
sage: myfactors.sort()
sage: for f in myfactors[:10]:
....:     print f
....:     
x^9 + x + 1
x^9 + x^4 + 1
x^9 + x^4 + x^2 + x + 1
x^9 + x^4 + x^3 + x + 1
x^9 + x^5 + 1
x^9 + x^5 + x^3 + x^2 + 1
x^9 + x^5 + x^4 + x + 1
x^9 + x^6 + x^3 + x + 1
x^9 + x^6 + x^4 + x^3 + 1
x^9 + x^6 + x^4 + x^3 + x^2 + x + 1

The code is "python-like", object-oriented, and the user has an easy game in the i(ron)python console. For instance, for a given instance of some object, using the dot-method, and hitting the TAB, one gets a list of all possible methods. For each method, putting a question mark after it, one gets the help (with examples). The community is active and open, open code makes this possible: asksage

Best Answer

Related Solutions

[Math] Characterization of irreducible polynomials over finite fields

Irreducible Polynomials over Finite Prime Fields

Related Question