# Inverse of a polynomial using long division over GF(256)

I am trying to find the inverse of a polynomial $3x^3+x^2+x+2$ over the field $GF(2^8)$ with polynomial $(x^4-1 )$

Here is what I did,

$$\dfrac{(x^4-1)}{3x^3+x^2+x+2}$$

$$(x^4-1) = (171x+199)(3x^3+x^2+x+2)+ (142x^2+227x+115)$$ $$\dfrac{(3x^3+x^2+x+2)}{(142x^2+227x+115)}$$

But I can not divide further because 142 does not provide me odd multiples to cancel $3x^3$. Can I use fractional number to get rid this? I tried fractional number too, but they made its too much complicated.

How can I do this? Or I am following a wrong approach?

• Are you sure of "over the field $GF(2^8)$ with polynomial $(x^4−1)$"? That polynomial is supposed to be a binary irreducible polynomial of degree 8, right? – fgrieu Jul 7 '17 at 8:45
• @fgrieu I am doing it for AES, as in AES Mixcolumn step as it states **Each column is treated as a four-term polynomial in which the coefficients are element over GF(2^8) and is then multiplied modulo $(x^4+1)$ with a fixed polynomial $3x^3+x^2+x+2$ the inverse of this polynomial is $11x^3+13x^2+9x+14$. ** – Sajid Khan Jul 7 '17 at 8:56

I think the root of the misunderstanding is that there are two completely disjoint notions of polynomials at work here.

First there is the finite field $\mathbb{F}_{2^8}$. It's the field where coefficients like "3" live. Following the AES notations, you represent these elements as integers, but they really are finite field elements. The definition of the finite field usually involves polynomials (of degree less than 8 and with coefficients in $\mathbb{F}_2$) but that's best viewed as a matter internal to that field.

Then the question you are trying to solve is about polynomials whose coefficients are themselves elements of $\mathbb{F}_{2^8}$. These polynomials are not at all the same polynomials as the ones used internally by $\mathbb{F}_{2^8}$.

Apparently you are trying to do computations with the coefficients (the ones in $\mathbb{F}_{2^8}$ as if they were integers, so your numbers are off. Let's see things in details:

You want to divide $x^4-1$ by $3x^3+x^2+x+2$. Not that in $\mathbb{F}_{2^8}$, addition really is XOR, so subtraction is the same as addition; thus, $x^4-1$ is also $x^4+1$. But anyway, in the course of the division, you want to "cancel out" the top coefficient of $x^4-1$ with a multiple of $3x^3+x^2+x+2$. In $\mathbb{F}_{2^8}$, $3\times246 = 1$, so you can write:

$$x^4 - 1 = 246x(3x^3+x^2+x+2) - 246x^3 - 246x^2 - 247x - 1$$

Next step is to cancel out this spurious $-246x^3$. Again, take care that this "$-246$" is not an integer; it is a field element in $\mathbb{F}_{2^8}$. Also, since (again) addition is XOR in that field, we can remove the minus sign (in binary fields $\mathbb{F}_{2^m}$, $z = -z$ for all elements $z$). Acknowledging that additions and subtractions are the same thing in a binary field, we can write this:

$$x^4 + 1 = 246x(3x^3+x^2+x+2) + 246x^3 + 246x^2 + 247x + 1$$

In the field, $246 = 82\times 3$ (yeah, for once, this matches integer multiplication, but it is fortuitous). So we can write this:

$$x^4 + 1 = (246x + 82)(3x^3 + x^2 + x + 2) + 164x^2 + 165x + 165$$

So the first "long division" in the Extended Euclidean Algorithm yields a quotient of $246x+82$, and the remainder is $164x^2+165x+165$.

Next step in the Extended Euclidean Algorithm will be to divide $3x^3+x^2+x+2$ by $164x^2+165x+165$. And that one will begin by dividing $3$ by $164$ in the field $\mathbb{F}_{2^8}$. The result of that division is $138$; that is, in the finite field: $3 = 164\times 138$. Computing out the division, we get:

$$3x^3 + x^2 + x + 2 = (138x + 79)(164x^2 + 165x + 165) + 79x + 168$$

I am too lazy to finish it by hand. The crucial point to understand is that all computations on coefficients are in $\mathbb{F}_{2^8}$, which is a finite field with its own rules, which are not the same rules as integers, even though they are represented as integers. In particular, there should be no notion of "odd integer".

Here is a piece of C code that implements computations in $\mathbb{F}_{2^8}$:

static unsigned
{
return x ^ y;
}

static unsigned
mul(unsigned x, unsigned y)
{
unsigned z;
int i;

z = 0;
for (i = 0; i < 8; i ++) {
z ^= x & -(y & 1);
y >>= 1;
x <<= 1;
x ^= (0x11B & -(x >> 8));
}
return z;
}

static unsigned
invert(unsigned x)
{
unsigned z;
int i;

z = x;
for (i = 0; i < 6; i ++) {
z = mul(z, z);
z = mul(z, x);
}
return mul(z, z);
}

static unsigned
divide(unsigned x, unsigned y)
{
return mul(x, invert(y));
}


In this code, every element of $\mathbb{F}_{2^8}$ is represented as an integer in the $0$ to $255$ range (0xFF is $255$). As you see, addition really is XOR (the C operator ^ is bitwise XOR). Multiplication is done bit by bit; the weird-looking code:

                x <<= 1;
x ^= (0x11B & -(x >> 8));


is really a "left shift" of x in $\mathbb{F}_{2^8}$ (try to work out why it works, it's enlightening). Finally, inversion (invert() function) is done with exponentiation: since there are exactly $255$ invertible elements in $\mathbb{F}_{2^8}$ (all except $0$: it's a field), then the inverse of $z$ is $z^{254}$ for all elements $z\neq 0$. The invert() function computes $z^{254}$ by repeated squarings and multiplications. (Note: that invert() function will happily compute the inverse of $0$ as $0$, even though $0$ is not invertible.)

• Thank you so much for you help. I got stuck here for more than 3 weeks. Finally now I am able to do it. Again Thank you. – Sajid Khan Jul 10 '17 at 7:45

You are trying to find an inverse for an element, that's not in the $GF(2^8)$ field. Polynomials in this field do have coefficients in $\in \{0,1\}$. I don't know, where your polynomial is coming from, but I think you should first map the polynomial into the field by doing $\mod 2$ on every coefficient: $x^3 + x^2 + x$

• I am doing it for AES, as in AES Mixcolumn step, it states Each column is treated as a four-term polynomial in which the coefficients are element over $GF(2^8)$ and is then multiplied modulo $(x^4+1)$ with a fixed polynomial $3x^3+x^2+x+2$ the inverse of this polynomial is $11x^3+13x^2+9x+14$. – Sajid Khan Jul 7 '17 at 9:01