# Extended Euclidean Algorithm in bit representation problem

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 :)

-
For some basic information about writing math at this site see e.g. here, here, here and here. – Julian Kuelshammer Nov 4 '12 at 12:27
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. – Hurkyl Nov 4 '12 at 12:36

## 1 Answer

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.

-
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. – sperners lemma Nov 4 '12 at 12:30
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. – sperners lemma Nov 4 '12 at 12:35
Thanks for mentioning Blankinship's algorithm! I'd never heard of it, but was able to implement it in Python for GF2 very easily. – Jason S Oct 3 '13 at 2:18