1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 )
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.