2
$\begingroup$

I want to construct a field with $8$ elements and a field with $27$ elements for an ungraded exercise.


For $\bf 8$ elements: So we can't just have $\Bbb Z/8\Bbb Z$ since this is not even an integral domain. But rather we can construct $\Bbb F_2 \oplus \Bbb F_2 \oplus\Bbb F_2 \oplus \Bbb F_2 = \{0,1,\alpha,\alpha+1,\beta,\beta+1,\gamma,\gamma+1\}$.

This line of thinking seems to break from what I tried. Is there a better way to construct these things?

I saw this answer: Construct a finite field of order 27

We pick a polynomial irreducible polynomial and take the quotient of $\Bbb Z_3[x]$ but this wasn't helpful in me understanding the general ideal/method.

$\endgroup$
  • 4
    $\begingroup$ That's precisely the general method. To construct a field of order $p^{n}$, you find an irreducible polynomial $p(x) \in \mathbb{F}_{p}[x]$ of degree $n$. The quotient field $\mathbb{F}_{p}[x]/p(x) \cong \mathbb{F}_{p}^{n}$. Also, a product of fields is not a field. In particular, your example is not isomorphic to the field with $8$ elements. $\endgroup$ – Alex Wertheim Oct 11 '15 at 6:59
  • $\begingroup$ Note that if $\mathbb{F}$ is a field, the polynomial ring $\mathbb{F}[x]$ is a principal ideal domain (actually a Euclidean domain). So if $p(x)$ is an irreducible polynomial in that ring, the principal ideal generated by $p(x)$ is a maximal ideal (and $\mathbb{F}[x]/p(x)$ is a field). $\endgroup$ – hardmath Oct 11 '15 at 7:13
  • $\begingroup$ In the second section of this answer you see a copy of $\Bbb{F}_8$ together with examples of its arithmetic. I'm not sure it answers your question well, but it gives you something to chew. As an additive group it is a direct sum of three copies of $\Bbb{F}_2$ - not four as in your attempt. That 4-way direct sum has 16 elements. You left out guys like $\alpha+\beta$, $\alpha+\gamma+1$ et cetera. $\endgroup$ – Jyrki Lahtonen Oct 11 '15 at 7:40
  • $\begingroup$ I’ve found that it seems rather easy to find a degree-$n$ irreducible over a finite field just by blind trial and error. $\endgroup$ – Lubin Oct 11 '15 at 18:48
3
$\begingroup$

There are two ways you might want to represent a field of order $q^k$ (where $q\in \mathbb{N}$ is a prime and $k \gt 0$ a positive integer).

One is to imagine a simple algebraic field extension of $\mathbb{Z}_q$ which has a basis $\{1,\alpha,\ldots,\alpha^{k-1}\}$, namely $\mathbb{Z}_q[\alpha]$ where $\alpha$ satisfies an irreducible monic polynomial of degree $k$ over $\mathbb{Z}_q$:

$$ \alpha^k + c_1 \alpha^{k-1} + \ldots + c_{k-1}\alpha + c_k = 0 $$

Any element of this field extension can be represented in terms of the basis, and the addition is just the same as the addition of the $k$-dimensional vector space over $\mathbb{Z}_q$. But when we multiply, we have to perform substitutions to eliminate powers $\alpha^k$ and higher by using:

$$ \alpha^k = - c_1 \alpha^{k-1} - \ldots - c_{k-1}\alpha - c_k $$

The other way to think about it is to start with an irreducible polynomial $p(x)$ of degree $k$ over $\mathbb{Z}_q$ and construct $\mathbb{Z}_q[x]/p(x)$ as a quotient ring. Since the ideal generated by $p(x)$ is maximal, the quotient ring is a field and has dimension $k$ over $\mathbb{Z}_q$ as a vector space.

These two constructions are equivalent, with $\alpha$ being a root of:

$$ p(x) = x^k + c_1 x^{k-1} + \ldots + c_{k-1}x + c_k $$

and identified with $x \bmod{p(x)}$ in $\mathbb{Z}_q[x]/p(x)$.

It turns out that all field extensions of degree $k$ over $\mathbb{Z}_q$ are isomorphic, so as a computational convenience the irreducible polynomial $p(x)$ may be chosen to be simple in some way (e.g. having as few nonzero coefficients as possible).

It's not hard to come up with a monic irreducible polynomial of degree $3$ over $\mathbb{Z}_2$ in order to construct a field of $8$ elements. You only need to check for divisibility by linear (first degree) factors to be sure of irreducibility.

$\endgroup$
  • $\begingroup$ Nice answer +1 for that. $\endgroup$ – Arnab Chatterjee. May 22 '18 at 10:10
2
$\begingroup$

Let $p$ be some prime and $k$ some natural exponent.

The field $\mathbb F_{p^k}$ can be thought of as a splitting field of $χ = X^{p^k} - X$ over $\mathbb F_p$.

There is a general way to construct splitting fields for any set of polynomials, in your case you just repeatedly construct $F[X]/(f)$ for some irreducible non-linear factor $f$ of $χ$ and some field $F$ you wish to extend. You start with $F = \mathbb F_p$, see here.

$\endgroup$
  • $\begingroup$ Do we ever need more than a single irreducible factor $f$ of degree $k$? $\endgroup$ – hardmath Oct 12 '15 at 0:03
  • 1
    $\begingroup$ @hardmath No, but the existence of such a factor is not obvious. The only way of proving it that I see at the moment is to already use the existence of a field with $p^k$ elements: Take a cyclic generator of its multiplicative group. Then it also generates the whole field, so its minimal polynomial has degree $k$, which therefore is an irreducible factor of $χ$ of degree $k$. But this would be kind of putting the cart before the horse. $\endgroup$ – k.stm Oct 12 '15 at 7:04
  • $\begingroup$ The nym of the OP (Galois in the Field) makes me wonder how much they already know about such things. $\endgroup$ – hardmath Oct 12 '15 at 14:51
  • $\begingroup$ @hardmath That’s also why I left that out. $\endgroup$ – k.stm Oct 12 '15 at 15:05
0
$\begingroup$

Use Zech logarithms. For primitive a, compute 1+a^k = a^Z(k). See Collected Algorithms of the ACM 1973 Lam and McKay. Arithmetic over a finite field. Number 469.

$\endgroup$
  • $\begingroup$ Given your enthusiasm for this approach, perhaps you would care to elaborate on what is meant by Zech logarithms? I believe a more detailed discussion would be critical to most Readers for proper appreciation of the suggestion. $\endgroup$ – hardmath Oct 12 '15 at 0:01

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.