0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Please use MathJax to make your question readable. Start by putting $ signs around the math expressions. $\endgroup$ – saulspatz Mar 10 at 10:43
  • $\begingroup$ Changed it, sorry didnt realize that at first.. $\endgroup$ – hassan zaidi Mar 10 at 10:54
  • $\begingroup$ Welcome to Maths SX! What is $x$ here? $\endgroup$ – Bernard Mar 10 at 12:51
  • $\begingroup$ 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) $\endgroup$ – hassan zaidi Mar 10 at 12:58
  • $\begingroup$ 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 $\endgroup$ – hassan zaidi Mar 10 at 12:59
2
$\begingroup$

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\ $.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – hassan zaidi Mar 10 at 16:31
  • $\begingroup$ 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. $\endgroup$ – lonza leggiera Mar 11 at 8:48
  • $\begingroup$ 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. $\endgroup$ – hassan zaidi Mar 11 at 11:28

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.