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?
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
add(unsigned x, unsigned y)
{
        return x ^ y;
}

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

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

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

        z = x;
        for (i = 0; i &lt; 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 &lt;&lt;= 1;
                x ^= (0x11B &amp; -(x &gt;&gt; 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.)