# Found $x^8$ while calculating inverse of $(x^6+1)$ in finite field $GF(2^8)$. Help???

So I was running the EEA (Extended Euclidean Algorithm) to find the multiplicative inverse of $$(x^6+1)$$ in the finite field $$GF(2^8)$$. Everything was going fine until the second last iteration where I was supposed to get my $$t(x)$$ auxiliary polynomial that was going to be the inverse. However, this is what I got: $$1=(x+1)-1(x) =(r_1+x^2 r_0+x^4 r_1+xr_0+x^3 r_1)+x(x^5 r_0+x^4 r_0+x^3 r_0+x^2 r_0+r_0+x^7 r_1+x^6 r_1+x^5 r_1+x^4 r_1+x^3 r_1+x^2 r_1+xr_1)$$ This equated to $$(x^6+x^5+x^4+x^3+x^2 ) r_0+(x^8+x^7+x^6+x^5+x^3+1)r_1$$ But as much as I know, there shouldn't be a value greater than x^7 in the polynomial, should there? Please Help I need to submit an assignment day after tomorrow...

(EDIT) enter image description here This is an image of the EEA calculations

• Please use MathJax to make your question readable. Start by putting $ signs around the math expressions. – saulspatz Mar 10 at 10:43 • Changed it, sorry didnt realize that at first.. – hassan zaidi Mar 10 at 10:54 • Welcome to Maths SX! What is$x$here? – Bernard Mar 10 at 12:51 • x is just a variable, that shows the bit value in an 8-bit vector. So, for example, the polynomial $$x^7+x^6+x^5+x^4+x^3+x^2+x$$ in bit value is (11111110) – hassan zaidi Mar 10 at 12:58 • Btw in the look up table the inverse is actually equal to (11111110) meaning that the 4th iteration's $$r_1$$ is the correct answer – hassan zaidi Mar 10 at 12:59 ## 1 Answer Judging from the calculation at the link you provided, you're taking $$\ x\$$ to be a root of the polynomial $$\ x^8 + x^4 + x^3 + x + 1\$$. There's nothing particulary wrong about having terms of degree $$8$$ or more in an expression for the inverse of an element of the field, but you can always replace them with a combination of terms of smaller degree by using the equation $$\ x^8 = x^4 + x^3 + x + 1\$$. As it happens, when I multiplied your putative inverse $$\ x^8+x^7+x^6+x^5+x^3+1= x^7+x^6+x^5+x^4+x\$$ by $$\ x^6+1\$$ I didn't get $$1$$. I got $$\ x^5\$$ instead. In fact, there appears to be an error on line $$2$$ of the calculation pointed to by your link. I believe the remainder on the right side of the equation should be $$\ x^4 + x^3 +x^2 + x + 1\$$ rather than $$\ x^4 + x^3 + x + 1\$$. • Yes you are right there was a problem in line 2, however, it was only a mistake of not writing the $$x^2$$ and I'm saying that because I rechecked my calculation twice after you pointed it out. And yes you are right $$x^7+x^6+x^5+x^4+x$$ is not the correct inverse of $$x^6+1$$ the correct inverse I got from a look table was actually $$x^7+x^6+x^5+x^4+x^3+x^2+x$$ . And I get it now that we can write the >8 terms using smaller degrees, but still, I don't quite understand why I'm not getting the correct answer. And btw this is of tremendous help. – hassan zaidi Mar 10 at 16:31 • I suggest you check your calculation of the coefficient of$\ r_1\ $in the second column of line 5. According to my calculations this should be$\ \left(x^4+x^3+1\right)\left(x^3+x\right) + x^2\ \$, which gives me a different result from what you have. – lonza leggiera Mar 11 at 8:48
• Guys this was extremely helpful and I'd like to thank everyone that commented. I realized my mistake, it was in the 5th iteration. The coefficient that was next to $$r_0$$ was written as $$x^8+x^7+x^6+x^5+x^3+1$$ when it was actually $$x^8+x^7+x^6+x^5+x^2+1$$. Thank you all for the comments. – hassan zaidi Mar 11 at 11:28