Extended Euclidean Algorithm in bit representation problem

Question

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

Answer 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.