Score:0

Find multiplicative inverse in Galois field $2^8$ using extended Euclides algorithms

sx flag

I'm dealing with Galois fields $GF(2^{8})$ and need help finding a polynomial $r^{-1}(x)$ such that $r^{-1}(x) r(x) \equiv 1 \mod m(x)$, where:

  • $m(x) = x^{8} + x^{4} + x^{3} + x + 1$
  • $r(x) = u(x) - q(x) \cdot m(x)$
  • $u(x) = s(x) \cdot t(x)$
  • $s(x) = x^{7} + x^{5} + x^{4} + x$
  • $t(x) = x^{4} + x^{2} + 1$

Thus:

  • $u(x) = x^{11} + x^{8} + x^{6} + x^{4} + x^{3} + x$
  • $q(x) = x^{3} + 1$
  • $r(x) = -x^{7} - x^{4} - x^{3} + 1 \mod 2 = x^{7} + x^{4} + x^{3} + 1$

what I have tried

I've attempted to find out $r^{-1}(x)$ but failed.

Here is what I've tried:

From Euclides's algorithm:

\begin{align*} u(x) &= q(x) \cdot m(x) + r(x) \\ m(x) &= q_{2}(x) \cdot r(x) + r_{2}(x) \\ &= x \cdot r(x) + (-x^{5} + x^{3} + 1 \mod 2) \\ &= x \cdot r(x) + ( x^{5} + x^{3} + 1) \\ r(x) &= q_{3}(x) \cdot r_{2}(x) + r_{3}(x) \\ &= (x^{2} - 1 \mod 2) \cdot r_{2}(x) + (x^{4} + 2 x^{3} - x^{2} + 2 \mod 2) \\ &= (x^{2} + 1) \cdot r_{2}(x) + (x^{4} + x^{2}) \\ r_{2}(x) &= q_{4}(x) \cdot r_{3}(x) + r_{4}(x) \\ &= x \cdot r_{3}(x) + 1 \\ r_{3}(x) &= q_{5}(x) \cdot r_{4}(x) + r_{5}(x) \\ &= (x^{4} + x^{2}) \cdot r_{4}(x) + 0 \end{align*}

We have:

\begin{align*} q_{2}(x) &= x \\ q_{3}(x) &= x^{2} + 1 \\ q_{4}(x) &= x \\ q_{5}(x) &= x^{4} + x^{2} \\ r_{2}(x) &= x^{5} + x^{3} + 1 \\ r_{3}(x) &= x^{4} + x^{2} \\ r_{4}(x) &= 1 \\ r_{5}(x) &= 0 \end{align*}

Thus:

\begin{align*} 1 &= r_{4}(x) \\ &= r_{2}(x) - q_{4}(x)r_{3}(x) \\ &= r_{2}(x) - q_{4}(x)\big(r(x) - q_{3}(x)r_{2}(x)\big) \\ &= \big(-q_{4}(x)\big) r(x) + \big(1 + q_{3}(x)\big) r_{2}(x) \\ &= \big(-q_{4}(x)\big) r(x) + \big(1 + q_{3}(x)\big) \big(m(x) - q_{2}(x)r(x)\big) \\ &= \Big(-q_{4}(x) - q_{2}(x) - q_{2}(x)q_{3}(x)\Big) r(x) + \Big(1 + q_{r}(x)\Big) m(x) \end{align*}

So, we get:

\begin{align*} r^{-1}(x) & = - q_{4}(x) - q_{2}(x) - q_{2}(x)q_{3}(x) & \mod 2 \\ & = - x - x - x(x^{2} + 1) & \mod 2 \\ & = - x - x - x^{3} - x & \mod 2 \\ & = - x^{3} - 3x & \mod 2 \\ & = x^{3} + x \end{align*}

But, this is wrong because when I compute $r^{-1}(x) r(x) \mod m(x)$ the result is not 1

us flag
where does the "mod 2" come from?
blackyellow avatar
sx flag
@SamGinrich the mod 2 is because we are in $GF(2^n)$
us flag
$GF(2^n)$ is something modulo $m(x)$
blackyellow avatar
sx flag
Sorry, I didn't understand what I did wrong.. I do am having trouble understanding the algorithm (that's why i need help). I computed $\mod 2$ because I thought the polynomial coefficients had to be in $\{0,1\}$ since we're dealing with bytes. If you can explain what I did wrong I'd appreciate it!
fgrieu avatar
ng flag
I guess it's wanted the polynomial inverse of $s(x)\cdot t(x)$ modulo $m(x)$, and towards this you define $r(x)=s(x)\cdot t(x)\bmod m(x)$. Without this definition I fail to make sense of _thus_ $u(x)=s(x)\cdot t(x)$.
blackyellow avatar
sx flag
@fgrieu I forgot to mention that $u(x) = s(x) \cdot t(x)$ because it is defined this way in the problem
Score:1
ng flag

A problem is where $$r_{2}(x) - q_{4}(x)\big(r(x) - q_{3}(x)r_{2}(x)\big)$$becomes$$\big(-q_{4}(x)\big) r(x) +\big(1 + q_{3}(x)\big) r_{2}(x)$$when that should to be$$\big(-q_{4}(x)\big) r(x) +\big(1 + q_{4}(x)\cdot q_{3}(x)\big) r_{2}(x)$$


Independently, I think it would be best to use the significantly simpler algorithm there, which needs to keep track of only 4 variables.

blackyellow avatar
sx flag
Thank you! That was where I got wrong! God bless you because I was having so much stress with this question...
blackyellow avatar
sx flag
By the way, I implemented the simpler algorithm you talked about instead of the one I was using previously.... thanks!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.