finding all irreducible polynomials over $\mathbb{F}_3$ up to degree $2$, faster method? I want to find all irreducible polynomials over $\mathbb{F}_3$ up to degree $2$ and I wonder if there's a better method than the following.
The polynomials are of form $aX^2 + bX +c$. So I have to check $3\cdot3\cdot3=27$ polynomials. First, I write down the $6$ irreducible polynomials of order one $X, X+1, X +2, 2X, 2X+1, 2X+2$. The $3$ polynomials with $a=b=0$ are not irreducible by definition.
So I'm left with $18$ polynomials of degree 2. The $6$ polynomials with $c=0, a \neq 0$ are obviously reducible, so I'm left with $12$ polynomials. Checking if they have roots are $24$ operations.
 A: First, as also written in the comments, use the fact that $f$ irreducible iff $cf$ irreducible ($c\in\{\pm 1\}$) to reduce the search to monic polynomials. There remain the $9$ polynomials $f(x) = x^2 + ax + b$ with $a,b\in\mathbb F_3$.
Now we want to find the irreducible polynomials $f$.
Then $0$ is not a root, so $b\neq 0$ which leaves the $6$ polynomials with $a\in\mathbb F_3$ and $b\in\{\pm 1\}$.
Furthermore, $1$ is not a root, so $f(1) = 1 + a + b \neq 0$, and $-1$ is not a root, so $f(-1) = 1 - a + b \neq 0$.
This implies $a \neq \pm (1+b)$.
So for $b = 1$ we get $a = 0$, and for $b = -1$ we get $a \neq 0$.
The remaining polymomials are
$$
x^2 + 1,\quad x^2+x-1,\quad x^2-x-1\text{.}
$$
By construction, they don't have any roots in $\mathbb F_3$. Now by degree $2$, they are irreducible.
To get the full set of irreducible polynomials (not only the monic ones), we have to add the negative of each of these polynomials. In the end, there are $6$ irreducible polynomials over $\mathbb{F}_3$ of degree $2$.
