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
    For some basic information about writing math at this site see e.g. [here](http://meta.math.stackexchange.com/questions/5020/), [here](http://meta.stackexchange.com/a/70559/155238), [here](http://meta.math.stackexchange.com/questions/1773/) and [here](http://math.stackexchange.com/editing-help#latex).2012-11-04
  • 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
    I'm using fixed width text intentionally so the calculation is easier to read and check, please don't change it to LaTeX unless you can make all the digits line up the same way.2012-11-04
  • 0
    Note, "subtract" is just the same as "add", but I say it because we really do need to subtract and not add in cases other than Z/2Z.2012-11-04
  • 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