Is there a site that has tables of irreducible polynomials over Finite prime fields? Preferably up to at least degree 10 for primes 2, 3, and 5.
Also, what programming language is helpful in factoring polynomials over finite fields?
Irreducible Polynomials over Finite Prime Fields
finite-fields
Related Solutions
Recall that $$M(n, q) = \frac{1}{n} \sum_{d | n} \mu(d) q^{n/d}$$
is the number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_q$. The statement that there are $q^n$ monic polynomials of degree $n$ over $\mathbb{F}_q$ can then be written as the generating function identity $$\zeta(t) = \prod_{n \ge 1} \frac{1}{(1 - t^n)^{M(n, q)}} = \sum_{n \ge 0} q^n t^n = \frac{1}{1 - qt}$$
which is known as the cyclotomic identity and is the analogue for $\mathbb{F}_q[t]$ of the Euler product of the Riemann zeta function. If we instead want to count the number $s_n$ of squarefree monic polynomials of degree $n$ over $\mathbb{F}_q$, we want to work out the generating function $$\sum s_n t^n = \prod_{n \ge 1} (1 + t^n)^{M(n, q)}.$$
But by inspection this is just $$\frac{\zeta(t)}{\zeta(t^2)} = \frac{1 - qt^2}{1 - qt} = 1 + \sum_{n \ge 1} (q^n - q^{n-1}) t^n.$$
(The generating function identity $\zeta(t) = \zeta(t^2) \sum s_n t^n$ merely expresses the fact that every monic polynomial can be uniquely factored into its largest square factor and its squarefree part.)
Hence for $n \ge 1$ there are $q^n - q^{n-1} = \left( 1 - \frac{1}{q} \right) q^n$ monic squarefree polynomials of degree $n$ over $\mathbb{F}_q$. Jordan Ellenberg wrote a great blog post over at Quomodocumque explaining how this is related to the braid group and the analogous question about squarefree integers here.
(Note that you don't actually have to know the closed form of $M(n, q)$ for the above argument to work; I included it for the sake of concreteness.)
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.
Best Answer
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.
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