4
$\begingroup$

The finite field of order $p^n$ is isomorphic to $(\mathbb Z/p \mathbb Z)[X]/(P)$, where $P$ is an irreducible polynomial in $(\mathbb Z/p \mathbb Z)[X]$ of degree $n$. This describes every finite field up to isomorphism.

My question is, what are alternate ways of describing these finite fields?

For example, Conway gave an alternate way of describing the fields $GF(2^{2^n})$ (see this example answer).

$\endgroup$
6
  • 1
    $\begingroup$ Try $A/\mathfrak m$ for $A$ any finitely generated $\mathbf Z$-algebra and $\mathfrak m$ a maximal ideal in $A$. $\endgroup$
    – KConrad
    Commented Jun 8, 2018 at 21:15
  • $\begingroup$ @KConrad, as suggested perhaps by the username, it seems that @‍PyRulez might be searching for a computationally effective presentation. $\endgroup$
    – LSpice
    Commented Jun 8, 2018 at 23:04
  • $\begingroup$ Maybe you can define a multiplication on $\Bbb F_p^2$ via $ (x,y)(x',y') = (xx'-yy', xy' + x'y)$ and this might give you a field isomorphic to $\Bbb F_{p^2}$. $\endgroup$
    – Watson
    Commented Jun 12, 2018 at 19:54
  • $\begingroup$ @Watson, of course "maybe" here means "if and only if $p \equiv -1 \pmod4$" (i.e., if and only if $-1$ is not a square already in $\mathbb F_p$). $\endgroup$
    – LSpice
    Commented Jun 13, 2018 at 8:53
  • 1
    $\begingroup$ @LSpice : yes, obviously. I just wanted the OP to have a thought about it. $\endgroup$
    – Watson
    Commented Jun 13, 2018 at 9:28

6 Answers 6

2
$\begingroup$

In ONAG chapter 6, Conway gives a way of defining the finite field $2^{2^n}$ for any natural $n$. The domain is $\{0,1,\dots, 2^{2^n}-1\}$. Addition is defined by the two rules:

  1. The sum of $2^x$ and $2^y$ with $x \ne y$ is just the regular $2^n+2^m$. (So $13 = 8 + 4 + 1$.)
  2. The sum of two equal numbers is $0$.

Multiplication is likewise defined by two rules.

  1. The product of $2^{2^x}$ and $2^{2^y}$ with $x \ne y$ is just their ordinary product.
  2. The square of $2^{2^x}$ is the ordinary product of $\frac 32$ and $2^{2^x}$.

This uniquely defines the field. For example, using only the field axioms and above rules, we conclude $$5 \times 9 = (4+1)(4\times2+1) =\\ 4^2 \times 2 + 4 \times 2 + 4 + 1 = 6 \times 2 + 8 + 4 + 1 =\\ (4 + 2) \times 2 + 13 = 4 \times 2 + 2^2 + 13 =\\8 + 3 + 13 = 6$$

Also see this addition and multiplication table.

Conway goes on to extend this to the set $\{\alpha:\alpha < \beta\}$ for certain ordinals $\beta$, and to the class of all ordinals to create the curious Field $\text{On}_2$.

One nice thing about this construction is it shows show $GF(2^{2^n})$ is isomorphic to a subfield of $GF(2^{2^m})$ for any $n \le m$.

$\endgroup$
2
  • 2
    $\begingroup$ It seems a bit strange to post a question and an answer simultaneously. Rather, it probably makes more sense to make this part of the question itself, so that people can see what kind of answer you want (which wasn't clear to me from the question, at least). $\endgroup$
    – LSpice
    Commented Jun 8, 2018 at 20:34
  • 1
    $\begingroup$ @LSpice I edited the question to link to this answer. I thought the answer was a little big to include in the question. $\endgroup$ Commented Jun 8, 2018 at 20:36
2
$\begingroup$

Instead of having a single polynomial-quotient (aka “rupture”) step $\mathbb{F}_p[X]/(P)$ with $P \in \mathbb{F}_p[X]$ irreducible, you can also construct finite fields in several steps, i.e., construct first $\mathbb{F}_q = \mathbb{F}_p[X]/(P)$ with $P \in \mathbb{F}_p[X]$ irreducible and then the desired field as $\mathbb{F}_q[Y]/(Q)$ with $Q \in \mathbb{F}_q[Y]$ irreducible. (Even more generally, you can quotient $\mathbb{F}_p[X,Y]$ by a maximal ideal, though whether this is really different depends on what you mean by “different”, as a Gröbner basis for the lexigraphic ordering on monomials lets you write the latter as the former.) And of course you can have many such “rupture” steps.

This is, in fact, what happens for Conway's construction: $\mathbb{F}_{2^{2^{r+1}}}$ is constructed as the quotient of $\mathbb{F}_{2^{2^r}}$ by the Artin-Schreier polynomial $X^2 + X + c$ where $c$ is the element represented by $2^{2^r-1}$ (which is also the product, of the elements represented by $2^{2^i}$ for $0\leq i\leq r-1$), after what the element given by $a_1 X + a_0$ is represented by the integer $a_1 \cdot 2^{2^r} + a_0$, i.e., by juxtaposing the binary representations. So Conway's construction can be seen as an iteration of the quadratic rupture step given by an Artin-Schreier polynomial (constructing the A-S root of the “smallest” element $c$ which doesn't already have one).

Various people have given thought to the question of constructing the lattice of all finite fields (of a given characteristic) “uniformly” or “standardly”, or at least in a computably efficient way, by piling up rupture steps. For more about this, I can refer to Édouard Rousseau's 2021 PhD thesis “Arithmétique efficace des extensions de corps finis” [despite the title in French, most of the content is in English] and/or Frank Lübeck's paper “Standard Generators of Finite Fields and their Cyclic Subgroups”. The main issue is how to choose the rupture polynomials in a coherent way, and this can be seen as a generalization of Conway's construction.

$\endgroup$
1
$\begingroup$

It's only a tiny bit different, but if you put $\omega=\exp(2\pi i/(p^n-1))$ and $A=\mathbb{Z}[\omega]<\mathbb{C}$ then $A/pA$ is a product of fields, each of order $p^n$ (and therefore isomorphic to each other).

$\endgroup$
1
$\begingroup$

An alternate description that works for every finite field is the matrix representation: any finite field of order $q^m$ can be represented by a matrix algebra $\mathbb F_q[M]$ where $M$ is a $m\times m$ matrix with irreducible characteristic polynomial.

$\endgroup$
1
$\begingroup$

Another way of representing finite fields that is sometimes used on computational algebra is via Zech logarithms: basically you represent all non-zero elements as powers of a fixed primitive root $\alpha$ (i.e. a generator of the multiplicative group of the finite field $\mathbb{F}_q$). Then the Zech logarithm encodes for every element $\alpha^n$ its successor $\alpha^n+1 = \alpha^{Z(n)}$ (of course one also has to deal with the zero some element somehow, but I'll omit that for simplicity). Then using this you can implement addition by using that $\alpha^n + \alpha^m = \alpha^n (1+\alpha^{n-m}) = \alpha^n \alpha^{Z(n-m)} = \alpha^{n+Z(n-m)}$. Of course multiplication and inversion are trivial to implement, too.

For finite fields of moderate size storing the Zech logarithms as a table is cheap. For large field sizes this method is not very practical as the tables become big, and also finding a primitive element becomes difficult.

$\endgroup$
0
$\begingroup$

The field of $p^n$ elements is the splitting field of $x^{p^n}-x$ over the field of $p$ elements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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