7
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ Your field is now just $GF(3)[x]/\langle x^6+2x^2+1\rangle$. See this Wikipedia link. $\endgroup$ – TonyK Mar 25 '15 at 10:45
  • 2
    $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Mar 25 '15 at 17:28
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.