primitive polynomials of degree $d$ over $F_{3^3}$

Question

I am trying to find all primitive polynomials of degree $d$. Is there any list of them? We have to look each polynomial and decide which is primitive or not. Is it only way to find them?

Answer 1

Are you really, really asking for polynomials of degree $d$ over $\Bbb F_{27}$ whose roots are generators of the cyclic group $(\Bbb F_{27^d})^\times$?

Here’s how to do it for $d=2$.

First you have to describe $k=\Bbb F_{27}$ by finding an element that generates this field over the prime field $\Bbb F_3$, in other words, find a cubic irreducible over the prime field. $X^3-X-1$ will do, so you generate $k$ by an element $\alpha$ with $\alpha^3-\alpha-1$.

Then you have to describe $K=\Bbb F_{729}$ by finding an irreducible quadratic over $k$. Here, $X^2+\alpha$ will do, you’re just adjoining a square root of $-\alpha$. So you’re adjoining $\beta$, where $\beta^2+\alpha=0$.

Next, you have to put your hands on some generator $g$ of $K^\times$. You do this by trying $g^{728/2}=g^{364}$, $g^{728/7}=g^{104}$, and $g^{728/13}=g^{56}$. If all of these are unequal to $1$, your $g$ is a generator. I found the generator $g=\alpha^2+\alpha+\beta$.

All right, how do you find the $k$-minimal polynomial of an element $\gamma$ of $K$? This is the easiest part: calculate $(X-\gamma)(X-\gamma^{27})$, and that’s it. For instance, the minimal polynomial of $g$ itself is $X^2 + (\alpha^2+\alpha)X -\alpha^2+\alpha-1$.

Now you pull the same stunt for $\gamma=g^m$ where $m$ runs through the $\phi(728)=288$ different numbers between $1$ and $728$ that are relatively prime to $728$. (Actually, in this case, there are only $144$ numbers to check, because $m$ and $27m$ give the same polynomial. In general, at this stage you will get $\phi(27^{d})/d$ different polynomials.)

And there you are.

Do you really, really want to do this?