Explicitly construct a field with 729 elements

Question

I would like to construct a field with 729 elements. I know that $729 = 3^6$, and that I have to find an irreducible monic polynomial of degree 6 over $GF(3)$. I chose the polynomial $x^6 + 2x^2 + 1$, which I have verified (computationally) that it is irreducible over this field. However, I do not know how to proceed with the construction. Any hints?

Suppose I hadn't found this polynomial computationally. Is there an algebraic method of finding such polynomials when the degree is quite large? Or, at least testing for irreducibility in such cases?

Answer 1

Hint : If $F$ is a field then $F[x]/\langle{p(x)\rangle}$ is a field if and only if $p(x)$ is an irreducible polynomial over $F$.

Answer 2

As indicated above $GF_{729} \cong \Bbb Z_3[x]/\langle x^6 + 2x^2 + 1\rangle$. Additively, this is the same as the vector space $(\Bbb Z_3)^6$ and were it not for the need to multiply, we could let the matter rest there. The multiplication by multiplying cosets of polynomials is a bit unwieldy, so many prefer to find a "primitive element" (a generator of the cyclic group (of order $728$) of non-zero elements). Although the usual method is "trial-and-error", this is not as bad as it sounds, there are $288$ generators to be found. Finding such a primitive element $\alpha$ allows us to construct a "discrete logarithm table", turning products in $GF_{729}$ to sums in $\Bbb Z_{728}$.

Since $728 = 2^3\cdot 7 \cdot 13$ it suffices to check if $\alpha^k \equiv 1 $(mod $729$), for $k = 56,104,364$.

Checking for a polynomial that is irreducible of degree $n$ over $\Bbb Z_p[x]$ can be computationally expensive, algorithms do exists for generating them, but they are not "simple".