# Explicitly construct a field with 729 elements

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?

• Your field is now just $GF(3)[x]/\langle x^6+2x^2+1\rangle$. See this Wikipedia link. – TonyK Mar 25 '15 at 10:45
• You don't have to find an irreducible monic polynomial of degree$~6$ to construct $\Bbb F_{729}$. A two-step construction using irreducibles of degree $2$ and $3$ will do fine too. – Marc van Leeuwen Mar 25 '15 at 17:28

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$.
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".