Let's denote a polynomial of degree $k$: $f(x) = (a_1,\ldots ,a_k) := a_1x^k+\cdots +a_k$. Find all irreducible monic polynomials over $\mathbb{Z}_3$ of degree at most $4$.
For $\deg f = 1$, we have $f = (1,0),(1,1),(1,2)$. This serves as a generator for all Reducible monics of degree $2$. We have total of 6 ways to uniquely multiply them to obtain a monic of degree $2$ and since there are $9$ total, this leaves us $3$, thus:
For $\deg f=2$, we have $f = (1,0,1),(1,1,2),(1,2,1)$.
For $\deg f=3$, we have total of $27$ monics and the generator of reducibles of $\deg 3$ is the union of the irreducibles of $\deg 1$ and $\deg 2$ and so we have multiply them in "all possible ways" that yield something of degree $3$.
The counting gets messy here:
For degree $1$ irreducibles, we can cube each of them, $3$ ways. We can Square one and multiply by another, $6$ ways and we can multiply them all for a total of $10$ ways.
Since we want the product to be of degree $3$ , we need to multiply $\deg f=1$ irreducibles with $\deg f=2$ irreducibles, that gives us another $9$ possibilities.
Are there $19$ reducibles of degree $3$? (i.e 8 irreducibles?)
Concern: Are all these products unique, that is, do we count everything exactly once?
For $\deg f=4$, we can (hopefully) count analogously.
I can write tables for small degrees and test everything out by hand and find irreducibles in some amount of effort. What to do when we find all irreducibles of , say, at most degree $8$ over $\mathbb{Z}_{17}$?
Is there a quicker method of determining irreducibility or weeding out the irreducibles of a given degree? The end of goal is still explicitly finding all of them.
You can do the following: The Galois Group of $\mathbb{F}_{81}$ is the cyclic group $C_4$. There are $18$ orbits of size $4$, the others are of order $2$ or $1$. These orbit are of the form $\{z^k,z^{3k}, z^{9k}, z^{27k} \}$, for $z$ a primitive element and the exponents taken $\operatorname{mod} 81$. An irreducible polynomial is then given by $(z-z^k)(z-z^{3k})(z-z^{9k})(z-z^{27k})$.
EDIT after a comment of Jyrki Lahtonen
The elements of $\mathbb{F}_{81}$ are, by Galois theory, invariant for a subgroup $H$ of the Galois group $G$, there is only such (non trivial) subgroup namely the sqyare of the generator of $G$, the Frobenius exponential map of order $3$. This means that we are to look out for values $k$ for which $z^k$ is invariant under the Frobenius map of order $9$, i.e. the $k$ for which $$ z^{9k} = z$$, or, equivalently $z^{8k} = 1$. Since the order of $z$ is $80$ this gives rise to the values $k \in \{10, 20, 30, 40, 50, 60, 70, 80\}$ .