4
$\begingroup$

Hi guys I have a question regarding EEA. I know how to do the standard EEA for when $r_0$ and $r_1$ are in integers but I don't know how to apply it for when the numbers are in bit form. The question is

"Determine the multiplicative inverse of $x^7+x^2+1$ in $\operatorname{GF}(2^8)$ induced by irreducible polynomial $m(x)= x^8+x^7+x^3+x+1$."

I know that $x^7+x^2+1= 1000 0101$ and $x^8+x^7+x^3+x+1= 1 1000 1011$ but how do I proceed on with EEA? Do i convert the bits to integer? If i convert the bits to integer, then i will get $-98 \mod 395$ as my answer, but the answer is $x^6+x^5+x$ which is $98$ instead?

Thanks for any help rendered :)

  • 0
    The question isn't about using the EEA for numbers. It's about doing it for *polynomials* over $GF(2)$. While representing such polynomials by integers is needed for low-level programming, that *really* isn't how you should be thinking about what you're doing.2012-11-04

1 Answers 1

1

So the idea is that arithmetic in $GF(2)$ is the same as arithmetic in the quotient of $(\mathbb Z/2\mathbb Z)[x]$ by $(x^8+x^7+x^3+x+1)$.

Remember to compute the multiplicative inverse of a number, say $7$ in the field $\mathbb Z$ quotiented by $11\mathbb Z$, we can solve the diophantine equation $7a + 11b = 1$ with $(a,b)$ in $\mathbb Z$ using EEA. It's the same here, we find the multiplicative inverse by solving the equation $(x^7+x^2+1)a + (x^8+x^7+x^3+x+1)b = 1$ with $(a,b)$ in $(\mathbb Z/2\mathbb Z)[x]$.

The best way to use EEA in practice (for numbers as well as polynomials) is by BlankinShip's Algorithm. I like that idea of writing the polynomials as 10000101 and 110001011 so let's use that notation.

/  10000101  1  0 \ \ 110001011  0  1 /  the first row op is to subtract the second row by 11 times the first  /  10000101   1  0 \ \       100  11  1 /  now we need to subtract the first row by 100001 times the first  /  1    1100010 100001 \ \  100       11      1 /  and we are done! So let us just check (if we were confident in our ability it would not be necessary to check) that  10000101*1100010 + 110001011*100001 = 1  it does, so now reducing this equation mod 110001011 gives us 

$(x^7+x^2+1)\cdot(x^6+x^5+x) = 1 $ in GF(2)


notes on programming: If you implement polynomials in this binary way then addition would be implemented by the XOR operation. Overflow should not be a problem because the numbers only decrease in size during execution of the algorithm.

  • 0
    Thanks for mentioning Blankinship's algorithm! I'd never heard of it, but was able to implement it in Python for GF2 very easily.2013-10-03