I am trying to compute the multiplicative inverse of:
$x^4 + x^2 + x$
Using the irreducible polynomial:
$x^8 + x^4 + x^3 + x + 1$
Over $GF(2)=\mathbb{F}_2$.
I tried applying the extended euclidean algorithm but to no avail. At some point during the algorithm I end up with the remainder $169/144$ and am unsure how to proceed from there on. Any help would be greatly appreciated.
Thanks in advance!
$\mathbb{F}_2[x]/(x^8+x^4+x^3+x+1) \cong \mathbb{F}_{2^8}$.
If $\alpha \in \mathbb{F}_{2^8}$ and $\alpha\ne0$, then $\alpha^{2^8-1}=1$, and so $\alpha^{-1}=\alpha^{2^8-2}$.
Therefore, the inverse of $x^4 + x^2 + x$ in $\mathbb{F}_{2^8}$ is $(x^4 + x^2 + x)^{2^8-2}$.
This is an answer, even if not a very practical one.
The extended Euclidean algorithm (*) gives $$ 9= (12 x^7 - 15 x^6 + 9 x^5 - 6 x^4 + 18 x^3 - 6 x^2 - 6 x + 12)(x^4+x^2+x)+(-12 x^3 + 15 x^2 - 21 x + 9)(x^8+x^4+x^3+x+1) $$ from which we get that the inverse of $x^4+x^2+x$ is $12 x^7 - 15 x^6 + 9 x^5 - 6 x^4 + 18 x^3 - 6 x^2 - 6 x + 12=x^6 + x^5$.
(*) computed by WA.
