Revision history [back]

Here is a first brute force solution. I will use q instead of b. Let $F=\Bbb F_q=$GF(q) be the field with $q$ elements. One can use itertools.product (the pythonic way) or the sagemath specific cartesian_product to have a loop over (the tuples of) monic polynomials. We will collect only the irreducible ones of degree $a$ in $F[t]=\Bbb F_q[t]$.

q, a = 9, 5    
# feel free to use other values, 
# or arrange for a function to use an adapted code working in the following manner.

F = GF(q, names='w')
R.<t> = PolynomialRing(F)

all_polynomials = [
    t^a + sum([coeff*t^c for (c, coeff) in enumerate(my_tuple)])
    for my_tuple in cartesian_product([F for counter in range(a)])
]

irreducible_polynomials = [pol for pol in all_polynomials if pol.is_irreducible()]

And we obtain after some time the wanted list irreducible_polynomials. How many polynomials are in there?

sage: len(irreducible_polynomials)
11808

And which is the number we expect? Well, every polynomial in the list has $a=5$ roots which are not elements of a proper subfield of $\Bbb F_{9^5}$. There is only one proper subfield of $\Bbb F_{9^5}$, which is $\Bbb F_9$. (In general, we have all $\Bbb F_{q^d}$ for $d \ne a$ a divisor of $a$. These fields may have common elements, and the divisibility graph of $a$ mimic the intersection scheme of these fields.) So there are exactly $9^5-9$ elements of degree $5$ over $F=\Bbb F_9$, and collecting them in conjugacy groups (irreducible polynomials) we obtain $(9^5-9)/5=11808$ such groups.

We may also use this counting scheme to have an other way to generate the irreducible polynomials.

The above can be shortened to generate all monic irreducible polynomials by using instead the loop over the iterator R.polynomials(...):

q, a = 9, 5
F = GF(q, names='w')
R.<t> = PolynomialRing(F)

irreducible_polynomials = [
    t^a + pol 
    for pol in R.polynomials(max_degree=a - 1)
    if (t^a + pol).is_irreducible()
]

If the monic assumption is not needed, then all the irreducible polynomials of degree $a$ are alternatively given by:

q, a = 9, 5
F = GF(q, names='w')
R.<t> = PolynomialRing(F)

all_irreducible_polynomials = [
    pol 
    for pol in R.polynomials(of_degree=a)
    if pol.is_irreducible()
]

And we expect of course $(9-1)$ times $11808$ such polynomials, and producing them takes a lot of time. Indeed: