Multiplicative inverse in ${GF}(2^4)$

Question

I want to create a $4\times4$ multiplicative inverse table in $GF(2^4)$. The primitive polynomial given is $P(x)= x^4+x+1$

(NOTE: the values in the table need to be in hexadecimal format, hence I'll be using both polynomial and hexadecimal notations in the question henceforth).

Now, I was able to compute multiplicative inverse for the first row of the matrix i.e. (00,01,02,03). The inverse of 03 or $(x+1)$ comes out to be 0E or $(x^3+x^2+x)$.

However, when I try to compute the inverse of 10 or $x^4$, it again comes out to be 0E or $(x^3+x^2+x)$. Is it possible that two polynomials have exactly the same inverse? If not, I'm unable to figure out where I'm going wrong. Please help.

Answer 1

The Galois Field $\operatorname{GF}(2^4)$ (also represented $\mathbb{F_{2^4}}$) contains $16 = 2 ^4$ elements. The formal definition is;

$\mathbb{F_{2^4}}$ is the quotient ring $\mathbb{F_{2}}[X]/(x^4 = x + 1)$ of the polynomial ring $\mathbb{F_{2}}[X]$ by the ideal generated by $(x^4 = x + 1)$ is a field of order $2^4$.

We can list the elements of $\operatorname{GF}(2^4)$ on the polynomial representation with the defining primitive polynomial, namely $$a_3 x^3+a_2 x^2+a_1 x+a_0$$ where $a_i \in \operatorname{GF}(2)$ for $i=0,1,2,3$.

$\operatorname{GF}(2^4)$ is a Field therefore every element has a unique multiplicative inverse, except the zero.

$x^4$, as we can see, is not an element of the field, however, we can reduce it with the help of the defining polynomial's equation $x^4 = x + 1$. Therefore it has the same representation with $x+1$ in the field, so the inverse is the same.

Also, the multiplication inverse table has $2\times 16$ size, so there is only one row (or column ) to calculate.

\begin{array}{|c|c|}\hline p(x) \in GF(2^4) & inverse \\ \hline 1 & 1 \\\hline x & x^3 + 1 \\\hline x + 1 & x^3 + x^2 + x \\\hline x^2 & x^3 + x^2 + 1 \\\hline x^2 + 1 & x^3 + x + 1 \\\hline x^2 + x & x^2 + x + 1 \\\hline x^2 + x + 1 & x^2 + x \\\hline x^3 & x^3 + x^2 + x + 1 \\\hline x^3 + 1 & x \\\hline x^3 + x & x^3 + x^2 \\\hline x^3 + x + 1 & x^2 + 1 \\\hline x^3 + x^2 & x^3 + x \\\hline x^3 + x^2 + 1 & x^2 \\\hline x^3 + x^2 + x & x + 1 \\\hline x^3 + x^2 + x + 1 & x^3 \\\hline \end{array}

The non-zero elements of the field, usually represented by adding a star on the upper right $\mathbb{F}^*_{2^4} = \mathbb{F}_{2^4}- \{0\}$ form a multiplicative cyclic group. $\mathbb{F}^*_{2^4}$ can be generated by $x$, i.e. $\mathbb{F}^*_{2^4} = \langle x \rangle$. The powers of the generator;

\begin{array}{|c|c|}\hline i & x^i \\ \hline x^ 1 & x \\ \hline x^{ 2 } & x^2 \\ \hline x^{ 3 } & x^3 \\ \hline x^{ 4 } & x + 1 \\ \hline x^{ 5 } & x^2 + x \\ \hline x^{ 6 } & x^3 + x^2 \\ \hline x^{ 7 } & x^3 + x + 1 \\ \hline x^{ 8 } & x^2 + 1 \\ \hline x^{ 9 } & x^3 + x \\ \hline x^{ 10 } & x^2 + x + 1 \\ \hline x^{ 11 } & x^3 + x^2 + x \\ \hline x^{ 12 } & x^3 + x^2 + x + 1 \\ \hline x^{ 13 } & x^3 + x^2 + 1 \\ \hline x^{ 14 } & x^3 + 1 \\ \hline x^{ 15 } & 1 \\ \hline x^{ 16 } & x \\ \hline \end{array} $p(x) = 0$ is not included since it has no multiplicative inverse.

---

Below is the SageMath code used in this answer.

#Base field
R.<y> = PolynomialRing(GF(2), 'y')

#Defining polynomial
G = y^4+y+1

#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()

for p in S:
    if ( p != 0 ):
        print( p, " - ", 1/p )