Irreducible polynomials in $\mathbb F_3[x]$ 
Finding irreducible polynomials in $\mathbb F_3[x]$ of degree less or equal to $4$

for $d=2,3$ the polynomial should not have a root
case $d=2$ there are $2\cdot 3\cdot 3=18$ polynomials with degree $2$. Testing all I get;
$x^2+1, x^2+x+2, x^2+2x+2, 2x^2+2, 2x^2+x+1, 2x^2+2x+1$ are irreducible
when $d=3$ it gets complicated, at least by a theorem I know that there are $9$ irreducible monic polynomials ($x^{p^d}-x$ is the product of all irreducible monic polynomials in $\mathbb F_p[x]$)
Is there a technique to find these ?
here for example there is a complicated formula, which only determines the monic ones
 A: Here's a way to cut down on your work (but it still takes some work).
Degree 1: There are three irreducible monic polynomials of degree $1$: $x$, $x-1$, and $x+1$.
Degree 2: There are $9$ monic polynomials of degree $2$.  A polynomial of degree $2$ is irreducible iff it does not have $0$, $1$, or $-1$ as a root.  It is straight-forward to check these.  To make this a little faster, consider the following: $x^2+x+a$.  You can't have $a=0$ because then $0$ would be a root.  You can't have $a=1$ because then the coefficients would add to $0$ and $1$ would be a root.  You can have $a=2$, however, since the polynomial is not zero when $x=-1$.
Degree 3: There are $27$ monic polynomials of degree $3$.  A polynomial of degree $2$ is irreducible iff it does not have $0$, $1$ or $-1$ as a root.  Using the same trick as for degree 2, it is straightforward to find the irreducible monic polynomials of degree 3.
Degree 4: Observe that $x^2+1$ is irreducible of degree $2$.  Let $\alpha$ be a root of this polynomial in some extension.  If a degree $4$ polynomial is reducible, then it has one of $0$, $1$, $-1$, $\alpha$, $\alpha+1$, $\alpha-1$, $-\alpha$, $-\alpha+1$, or $-\alpha-1$ as a root.  Moreover, $\alpha$ has the property that $\alpha^2=-1$.  Therefore, you can also check for roots here.
There are other heuristics that help, but it's all tricks. 
A: You only need to consider monic irreducible polynomials (because if the leading coefficient is 2 then you can just multiply through by 2).
There are $3 \cdot 3 \cdot 3 = 27$ monic polynomials with degree 3.
You've found 3 degree-2 irreducible monic polynomials and there are 3 degree-1 irreducible monic polynomials ($x$, $x+1$, $x+2$).
Instead of counting irreducible degree-3 polynomials, let's count reducible ones. We can form a reducible polynomial by multiplying a degree-2 irreducible by a degree-1 irreducible, or by multiplying three degree-1 irreducibles.
In the first case, we have 9 reducible monic polynomials.
We need to be slightly more careful in the second case. We have 3 degree-3 monic irreducibles formed by cubing a degree-1. We have 6 formed by squaring a degree-1 and multiplying by a different one. We have 1 formed by multiplying them all together. This gives a total of 10 reducible monic polynomials.
Altogether this gives us 19 reducible monic polynomials, so we're looking for another 8, which should be the ones you haven't listed already! (This is also deducible more quickly but less directly from the formula in the link you sent. Note that $x^{p^d} - x = x(x^{p^d-1}-1)$, so your `theorem' isn't quite true as stated!)
You can play the same trick for degree-4: you can find all the reducible monic polynomials and deduce which are irreducible by a process of elimination.
There are often faster ad-hoc methods if you want to test if a given polynomial is irreducible, but I don't think that you can do better than this if you want to list all of the irreducible polynomials.
A: This doesn't answer your question, but it clarifies some of the statements in your question.
You can cut down a little of your work by just looking for monic polynomials.  Then, multiplying by coefficients $1$ and $2$.
To find all irreducible polynomials of degree less than or equal to $4$ in $\mathbb{F}_3[x]$, consider the polynomials $x^{3^n}-x$.
There are three irreducible monic polynomials of degree $1$, they are of the form $x-\alpha$.
There are three irreducible monic polynomials of degree $2$, since $x^{3^2}-x=x^9-x$ is the product of the three monic irreducible polynomials of degree $1$ and some number ($k$) of monic irreducible polynomials of degree $2$.  By counting degrees, we need $9=3+2k$ so there are $3$ irreducible monic polynomials of degree $2$.
By a similar argument, there are eight irreducible polynomials of degree $3$, since $x^{3^3}-x=x^{27}-x$ is the product of the three irreducible polynomials of degree $1$ and some number ($l$) of monic irreducible polynomials of degree $3$.  By counting degrees, we need $27=3+3l$ or that there are $8$ irreducible monic polynomials of degree $3$.
Finally, there are $18$ irreducible polynomials of degree $4$ since $x^{3^4}-x=x^{81}-x$ is the product of the three monic irreducible polynomials of degree $1$, the three monic irreducible polynomials of degree $2$, and the $m$ monic irreducible polynomials of degree $4$.  By counting degrees, this gives $81=3+3\cdot 2+4m$ or that $m=18$.  Therefore, there are $18$ irreducible monic polynomials of degree $4$.  (This could also be seen by noting that $\frac{x^{81}-x}{x^{9}-x}$ has degree $72$ and $72/4=18$).
For the small cases, it is sometimes easier to eliminate than to find.  For example, we know all of the irreducible monic polynomials of degree $1$.  We can multiply these together to get all reducible monic polynomials of degree $2$ (this is $6$ products of polynomials).  By looking for what's missing from the $9$ monic polynomials of degree $2$, you can find the monic irreducible polynomials of degree $2$.
For degree $3$, things get more complicated, but you're considering either products of three linear terms or a linear term with a degree $2$ factor.  Finally, for degree $4$, you want to eliminate products of the form: the product of $4$ linear terms, the product of two linear terms and a quadratic term, the product of a linear term with a cubic term, and the product of two quadratic terms.
