Discrete logarithm tables for the fields $Bbb{F}_8$ and $Bbb{F}_{16}$.

The smallest non-trivial finite field of characteristic two is $$\Bbb{F}_4=\{0,1,\beta,\beta+1=\beta^2\},$$ where $\beta$ and $\beta+1$ are primitive cubic roots of unity, and zeros of the polynomial $x^2+x+1$. Here the multiplication table is given once we know how to write the non-zero elements as powers of $\beta$. Extend the idea to fields of eight and sixteen elements.

Those fields can be constructed as $$\Bbb{F}_8=\Bbb{F}_2[\alpha], \quad\text{and}\quad \Bbb{F}_{16}=\Bbb{F}_2[\gamma],$$ where $\alpha$ has minimal polynomial $x^3+x+1$, and $\gamma$ has minimal polynomial $x^4+x+1$, both irreducible in $\Bbb{F}_2[x]$.

Task:

Calculate the tables for base $\alpha$ discrete logarithm of $\Bbb{F}_8$ and base $\gamma$ discrete logarithm of $\Bbb{F}_{16}$.

Answer

A (base-$g$) discrete logarithm of a finite field $\Bbb{F}_q$, is a function $$\log_g:\Bbb{F}_q^*\to\Bbb{Z}_{q-1}$$ defined via the equivalence $g^j=x\Leftrightarrow \log_g(x)=j$. For this to be well-defined it is imperative that $g$ is a primitive element, i.e. a generator of $\Bbb{F}_q^*$, and that the domain of $\log_g$ is the residue class ring of integer modulo $q-1$, as $g^{q-1}=g^0=1$.

It immediately follows that the discrete logarithm satisfies the familiar rules $$\begin{aligned} \log_g(x\cdot y)&=\log_g(x)+\log_g(y),\\ \log_g(x^n)&=n\cdot\log_g(x) \end{aligned}$$ for all elements $x,y\in \Bbb{F}_q^*$ and all integers $n$. The arithmetic on the r.h.s. is that of the ring $\Bbb{Z}_{q-1}$.

---

It is known that when $q=8$, a zero $\alpha$ of $x^3+x+1$ generates $\Bbb{F}_8^*$. This is proven by the following calculation, where we repeatedly use the fact that we are working in characteristic two, and that we have the relation $\alpha^3=\alpha+1$. $$\eqalign{ \alpha^0&=&&=1,\\ \alpha^1&=&&=\alpha,\\ \alpha^2&=&&=\alpha^2,\\ \alpha^3&=&&=1+\alpha,\\ \alpha^4&=&\alpha\cdot\alpha^3=\alpha(1+\alpha)&=\alpha+\alpha^2,\\ \alpha^5&=&\alpha\cdot\alpha^4=\alpha(\alpha+\alpha^2)=\alpha^2+\alpha^3=\alpha^2+(1+\alpha)&=1+\alpha+\alpha^2,\\ \alpha^6&=&\alpha\cdot\alpha^5=\alpha(1+\alpha+\alpha^2)=\alpha+\alpha^2+\alpha^3= \alpha+\alpha^2+(1+\alpha)&=1+\alpha^2,\\ \alpha^7&=&\alpha\cdot\alpha^6=\alpha(1+\alpha^2)=\alpha+\alpha^3=\alpha+(1+\alpha)&=1. }$$

We see from the end results in the last column that all the non-zero quadratic polynomials evaluated at $\alpha$ appear. This is yet another confirmation of the fact that $\alpha$ is a primitive element.

The discrete logarithm is used to replace the cumbersome multiplication (and raising to an integer power) of the field with more familiar integer arithmetic. Exactly like the old-timers used logarithm tables to replace the error-prone multiplication with the easier addition.

For example $$(1+\alpha)(1+\alpha+\alpha^2)=\alpha^3\cdot\alpha^5=\alpha^8=\alpha^7\cdot\alpha=\alpha.$$ Note that both the base-$\alpha$ discrete logarithms and its inverse mapping are needed. I generate such a table as a part of the program initialization, whenever I carry out extensive computer-aided calculations involving a finite field. The above table gives the discrete logarithm when read from right to left, and the inverse mapping (that we actually produced above) when read from left to right.

---

Similarly with $q=16$ we use $\gamma$, a zero of $x^4+x+1$. This time the table looks like $$\begin{aligned} \gamma^0&=&1\\ \gamma^1&=&\gamma\\ \gamma^2&=&\gamma^2\\ \gamma^3&=&\gamma^3\\ \gamma^4&=&\gamma+1\\ \gamma^5&=\gamma(\gamma+1)=&\gamma^2+\gamma\\ \gamma^6&=\gamma(\gamma^2+\gamma)=&\gamma^3+\gamma^2\\ \gamma^7&=\gamma^4+\gamma^3=&\gamma^3+\gamma+1\\ \gamma^8&=(\gamma^4)^2=&\gamma^2+1\\ \gamma^9&=\gamma(\gamma^2+1)=&\gamma^3+\gamma\\ \gamma^{10}&=\gamma^4+\gamma^2=&\gamma^2+\gamma+1\\ \gamma^{11}&=&\gamma^3+\gamma^2+\gamma\\ \gamma^{12}&=\gamma^4+\gamma^3+\gamma^2=&\gamma^3+\gamma^2+\gamma+1\\ \gamma^{13}&=\gamma^4+\gamma^3+\gamma^2+\gamma=&\gamma^3+\gamma^2+1\\ \gamma^{14}&=\gamma^4+\gamma^3+\gamma=&\gamma^3+1\\ (\gamma^{15}&=\gamma^4+\gamma=&1) \end{aligned}$$

Thus for example $$(\gamma^3+1)(\gamma^2+1)=\gamma^{14}\cdot\gamma^8=\gamma^{22}=\gamma^7=\gamma^3+\gamma+1.$$

---

As another example of the use of this table I want to discuss the problem of factorizing $x^4+x+1$ over $\Bbb{F}_4$. To that end we need to first identify a copy of $\Bbb{F}_4$ as a subfield of $\Bbb{F}_{16}$. We just saw that $\gamma$ is of order fifteen. Therefore $\gamma^5=\gamma^2+\gamma$ and $\gamma^{10}=\gamma^2+\gamma+1$ are third roots of unity. It is then trivial to check that we have a homomorphism of fields $\sigma:\Bbb{F}_4\to\Bbb{F}_{16}$ given by $\sigma(\beta)=\gamma^5$. Note that composing this (from either end) by the Frobenius automorphism gives an alternative embedding $\beta\mapsto \gamma^{10}$.

Basic Galois theory tells us that $$x^4+x+1=(x-\gamma)(x-\gamma^2)(x-\gamma^4)(x-\gamma^8)$$ as we get the other roots by repeatedly applying the Frobenius automorphism $F:x\mapsto x^2$. Here we see that the factor $$(x-\gamma)(x-\gamma^4)=x^2+x(\gamma+\gamma^4)+\gamma^5=x^2+x+\gamma^5$$ is stable under the automorphism $F^2$, and thus (as we also see directly!) has its coefficients in the subfield $\sigma(\Bbb{F}_4)$. The same holds for the remaining factor $$(x-\gamma^2)(x-\gamma^8)=x^2+x(\gamma^2+\gamma^8)+\gamma^{10}=x^2+x+\gamma^{10}.$$ Pulling back the effect of $\sigma$ we get the desired factorization $$x^4+x+1=(x^2+x+\beta)(x^2+x+\beta+1)$$ in $\Bbb{F}_4[x]$.

---

Here is a local version of similar tables for $\Bbb{F}_{256}$