# Irreducible polynomial roots and representations for Galois field elements in normal basis

I am trying to understand some topics in the literature and came across the following problem. Say I have a field $GF(2^4)$ defined by the irreducible polynomial $r(z) = z^4 + z + 1$, and I want to map an element in this field to an element in the isomorphic field $GF((2^2)^2)$ defined by the polynomials $p(x) = x^2 + x + 1$ and $q(y) = y^2 + y + (x + 1)$. Note that the coefficients in the polynomial $q(y)$ belong to the subfield $GF(2^2)$.

Now, I used Magma to find the following subset of roots for $p(x)$ and $q(y)$:

• $p(w + 1) = 0$, where $w + 1$ is in $GF(2^2)$
• $q(x + 1) = 0$, where $x$ is in $GF((2^2)^2)$

Now, assume I have an element $\alpha$ in $GF(2^4$ represented by 4 bits, namely, $\alpha_3\alpha_2\alpha_1\alpha_0$. In the standard (polynomial) basis, $\alpha$ is equivalent to $\alpha_3z^3 + \alpha_2z^2 + \alpha_1z + \alpha_0$. If I use the normal basis $[(w+1)^2, (w+1)]$ for elements in $GF(2^2)$ and $[(x+1)^4, (x+1)]$ for elements in $GF((2^2)^2)$, then we may rewrite $\alpha$ using new bits $g_i$ as follows:

$\alpha = \alpha_3z^3 + \alpha_2z^2 + \alpha_1z + \alpha_0 = (g_3(w+1)^2(x+1)^4 + g_2(w+1)(x+1)^4) + (g_1(w+1)^2(x+1) + g_0(w+1)(x+1))$

Now, if I simply compute $(w+1)(x+1), (w+1)^2(x+1), (w+1)(x+1)^2, (w+1)^2(x+1)^2$, I am under the impression that this is these are the new basis elements for $GF((2^2)^2)$, and so I should be able to easily derive a basis conversion algorithm by setting the binary strings of these products to be the column vectors of the matrix. This process yields the following:

\begin{matrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{matrix}

Unfortunately, using this basis transformation does not work. I verified its incorrectness by computing the square of some element $\alpha = z^3 + z + 1$ in $GF(2^4)$, and then by mapping $\alpha$ to its isomorphic counterpart in $GF((2^2)^2)$, computing the square in $GF((2^2)^2)$, and then mapping back to $GF(2^4)$. The results of these two steps did not match.

So, to summarize, I suppose my question is really three-fold. First, is my understanding of how the normal basis for an element in $GF((2^2)^2)$ is formed correct?

Second, is it enough to simply compute the products $(w+1)(x+1),\dots,(w+1)^2(x+1)^4$ and then map them to binary strings? Do I need to do any other sort of conversion?

Third, is my method of verification correct?

Thank you so very much to anyone who attempts to answer this question. There is a severe lack of consistency in the literature from which this problem arose, and I am simply trying to get everything along the same line. Also, my apologies for the length of this question.

If there is anything that is unclear, please comment and let me know.

• May be I missed it, but when did you identify a root of $r$ in terms of roots of $q$ and $p$? This is a must. I think the early part of my answer to another question might help you. Ignore the latter part where I try to do the same between $GF(256)$ and $GF(16^2)$. I couldn't make much sense of the paper (in that time) the asker referred to there, so I was unable to reproduce the formulas. But the passage between $GF(16)$ and $GF(4^2)$ should be ok. – Jyrki Lahtonen May 18 '13 at 4:42
• And something is strange in your notation. You denoted by $x$ a root of $p$ in $GF(4)$. And it appears as a coefficient of $q$. The element $x+1$ is then also in $GF(4)$, so it cannot be a zero of $q$, because $q$ has no zeros in $GF(4)$. In other words, I think that you are somehow misunderstanding Magma output. – Jyrki Lahtonen May 18 '13 at 4:46
• Please take a look at this question, too. – Jyrki Lahtonen May 18 '13 at 19:57
• Thank you, Jyrki. The answers to those questions certainly clear up many issues I was having. – caw May 21 '13 at 20:42

GF(2^4) primitive polynomial $$r(z) = z^4 + z + 1$$, primitive element α = x (hex 2)

GF((2^2)^2) primitive polynomial $$q(y) = y^2 + y + 3$$, primitive element β = x (hex 4)

GF(2^2) primitive polynomial $$p(x) = x^2 + x + 1$$, primitive element = x (hex 2)

Converting from GF(2^4) to GF((2^2)^2) can be done via a matrix multiply of a mapping matrix. The indexes to the columns of the mapping matrix correspond to the GF(2^4) values in hex {8 4 2 1}, which correspond to powers of α: α^{3 2 1 0} = {8 4 2 1}, and the values in each column are equal to powers of β: β^{3 2 1 0} = {b 7 4 1}. For the inverse matrix, used to map back from GF((2^2)^2) to GF(2^4), the indexes correspond to powers of β: β^{b 1 a 0} = {8 4 2 1} and the values in each column correspond to powers of α: α^{b 1 a 0} = {e 2 7 1}. The mapping matrix, it's inverse and the product of both are:

1 0 0 0    1 0 0 0     1 0 0 0
0 1 1 0    1 0 1 0     0 1 0 0
1 1 0 0    1 1 1 0     0 0 1 0
1 1 0 1    0 0 1 1     0 0 0 1

b 7 4 1    e 2 7 1     8 4 2 1


powers of α:
0 1 2 3 4 5 6 7 8 9 a b c d e
1 2 4 8 3 6 c b 5 a 7 e f d 9

powers of β:
0 1 2 3 4 5 6 7 8 9 a b c d e
1 4 7 b 5 3 c e 6 f 2 8 9 d a