I'm trying to calculate the inverse of $x^{7}+x^{5}+x^{4}+x^{2}+x+1$ over $\mathbb{Z}_{2}[x]/(x^{8}+1)$. I suspect there is something fundemental I'm misunderstanding about this process. I'm doing this using code I'm writing, verified by manual calculation, but it seems the problem is not with my code, but with my understanding of what needs to be done.
First of all, I tried applying the extended Euclidean algorithm, but I get that the GCD is $x+1$ (i.e. – that they are not coprime).
Also, as far as I can tell, $(x^{7}+x^{5}+x^{4}+x^{2}+x+1)*(x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x^{1}+1)=0$, suggesting it divides zero.
What am I misunderstanding?
Best Answer
I'm afraid the element you described has no inverse in the quotient ring $\Bbb{Z}_2[x]/\langle x^8+1\rangle$.
This is because your degree seven polynomial $f(x)=x^7+x^5+x^4+x^2+x+1$ shares a factor $x+1$ with $g(x)=x^8+1$. The easiest way of seeing this is to observe that $f(1)=0=g(1)$ so they are both divisible by $x-1=x+1$.
You can tell it at a glance because both polynomials have an even number of terms.
The quotient ring $\Bbb{Z}_2[x]/\langle g(x)\rangle$ is a field if and only if $g(x)$ is irreducible. When $g(x)$ is irreducible it obviously cannot have common factors with lower degree polynomials, and extended Euclid works like charm and finds the inverse.
A popular choice for a degree $8$ irreducible polynomial is $g(x)=x^8+x^4+x^3+x+1$ specified in Rijndael/AES crypto standard<.