Finding modular inverse of $x^4$ in $GF(2^5)\mod (x^5+x^2+1)$

Question

I cannot spot where I am going wrong in this. I am using Extended Euclidean's algorithm here.

$(x^5+x^2+1) = (x^4)(x) + (x^2+1)$

$(x^4) = (x^2+1)(x^2+1) + 1$

let $P(x)=x^4$ and $Q(x)=x^5+x^2+1$

$(x^5+x^2+1) + (x^4)(x) = (x^2+1)$

$(x^4) + (x^2+1)(x^2+1) = 1$

$P(x)+[Q(x)+P(x)(x)][Q(x)+P(x)(x)]=1$

$P(x)(1+xQ(x)+P(x)x^2+xQ(x)) +Q(x)(...)=1$

$P(x)(1+P(x)x^2)+Q(x)(...)=1$

$P(x)(1+x^6) + Q(x)(...)=1$

$(1+x^6) \bmod (x^5+x^2+1)=x^3+x+1$

I am getting the inverse of $x^4 \mod (x^5+x^2+1)$ as $x^3+x+1$ but it seems the right answer is $x^4+x^2+1$. Can anyone tell me where it is wrong?

Answer 1

Your answer is correct since, taking into account that the characteristic of the field is $2$, so that $x^5=x^2+1$, \begin{align} x^4(x^3+x+1)&=x^7+x^5+x^4=x^7+x^4+x^2+1 \\ &=x^2\cdot x^5+x^4+x^2+1=\color{red}{\not x^4}+\color{blue}{\not x^2}+\color{red}{\not x^4}+\color{blue}{\not x^2}+1\\ &=1. \end{align}

Answer 2

We want to solve $$x^4 \cdot (c_0 + c_1 x + c_2 x^2 + c_3 x^4) = 1$$

multiplying this out gives

\begin{align} & c_0 x^4 + c_1 x^5 + c_2 x^6 + c_3 x^8 \\ =&\, c_0 x^4 + c_1 (x^2 + 1) + c_2 (x^3 + x) + c_3 (x^3 + x^2) \\ =&\, c_1 + (c_1 + c_3) x^2 + (c_2 + c_3) x^3 + c_0 x^4 \\ \end{align}

so we want to solve the linear system:

• $c_1 = 1$
• $c_1 + c_3 = 0$
• $c_2 + c_3 = 0$
• $c_0 = 0$

to get our inverse $x + x^2 + x^3$