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

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.

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 )