Solution

Construct a Zech's Log Table for the finite field generated by $\alpha = x$ and the irreducible polynomial $f(x) = x^4 + x + 1$ with coefficients taken from $\mathbb{Z}_2$, and use it to write $y$ as a power of $x$, where

$$ y = x^{10} + \frac{x^7 + x^{23}}{x^4 + x^9} + 1 $$

First, we need to construct Zech's Log Table for this field.

Knowing that $f(x)$ allows us to reduce any polynomial down to a cubic, and abbreviating the general cubic $ax^3 + bx^2 + cx + d$ with the binary sequence "$abcd$" (so for example $x^3+x \rightarrow$ "$1010$"), we first compute the related binary sequences for $x, x^2, x^3, \ldots, $ and $x^{14}$.

Of course, we shouldn't have to compute any power higher than $x^{14}$ and can rest assured that $x^{15} = 1$, as we are told $\alpha=x$ is a generator.

To see this, note that the field so generated should have exactly $2^4 = 16$ distinct elements, before the powers of the generator start to repeat themselves (consider the number of possible binary sequences with 4 digits). Further, $0$ never shows up as a power of the generator $\alpha$ and $\alpha^0 = 1$, regardless of the choice of $\alpha$. This leaves $14$ remaining powers to compute: $x, x^2, x^3, \ldots, $ and $x^{14}$. After that, things should start repeating (suggesting $x^{15} = x^0 = 1$).

Finding these powers is quickly accomplished remembering that:

  • Coefficients come from $\mathbb{Z}_2$ and are thus combined modulo $2$, and
  • We can replace $f(x)$ with $0$ (or equivalently, we can replace any $x^4$ with $x+1$).
Consider the following examples: $$x^4 = x + 1 \rightarrow 0011$$ $$x^5 = x (x+1) = x^2 + x \rightarrow 0110$$ $$x^{10} = x^5 x^5 = (x^2+x)(x^2+x) = x^4 + 2x^3 + x^2 = (x+1) + 0x^3 + x^2 = x^2 + x + 1 \rightarrow 0111$$

Finally, to complete the table, for each exponent $i$, we find $z(i)$ so that $(1+x^i) = x^{z(i)}$

$$\begin{array}{|c|c|c|} \hline\\ \alpha^i & i & z(i) \\\hline 0000 & \infty & 0 \\ 0001 & 0 & \infty \\ 0010 & 1 & 4 \\ 0100 & 2 & 8 \\ 1000 & 3 & 14 \\ 0011 & 4 & 1 \\ 0110 & 5 & 10 \\ 1100 & 6 & 13 \\ 1011 & 7 & 9 \\ 0101 & 8 & 2 \\ 1010 & 9 & 7 \\ 0111 & 10 & 5 \\ 1110 & 11 & 12 \\ 1111 & 12 & 11 \\ 1101 & 13 & 6 \\ 1001 & 14 & 2\\\hline \end{array} $$ Then, $$\begin{array}{rcll} y &=& x^{10} + \frac{x^7 + x^{23}}{x^4 + x^9} + 1 \\\\ &=& x^{10} + \frac{x^7 (1+ x^{16})}{x^4 (1+ x^5)} + 1 \\\\ &=& x^{10} + \frac{x^7 (1+ x)}{x^4 (1+ x^5)} + 1 & \textrm{ (recall, $x^{15} = 1$) }\\\\ &=& x^{10} + \frac{x^7 x^4}{x^4 x^{10}} + 1 & \textrm{ (using the log table) }\\\\ &=& x^{10} + \frac{x^7}{ x^{10}} + 1 & \\\\ &=& x^{10} + \frac{1}{ x^{3}} + 1 & \\\\ &=& x^{10} + \frac{x^{15}}{ x^{3}} + 1 & \textrm{ (again recall, $x^{15} = 1$) }\\\\ &=& x^{10} + { x^{12}} + 1 & \\\\ &=& x^{10} (1 + x^2) + 1 & \\\\ &=& x^{10} x^8 + 1 & \textrm{ (again using the log table) }\\\\ &=& x^{18} + 1& \\\\ &=& x^3 + 1 &\\\\ &=& x^{14} & \textrm{ (after one final application of the log table) } \end{array}$$