# Thread: Extended Euclidean related polynomial's inverse

1. ## Extended Euclidean related polynomial's inverse

Hi My first post here,

I am very much confused, have wasted more than 7/8 hours on this single problem. But now I give up, can somebody please help me solve this. I do not yet know the correct answer to it, but what I am getting does not look right. Anyways, here is the problem:

Write down an analogue of the extended Eucliena Algorithm for the ring F2^[x]. Given that p(x) = x^8 + x^4 + x^3 + x + 1 is a (primitive) irreducible polynomial. Find the inverse of x^7 + x + 1 in the field

F2^8 = F2^[x]/(p(x)).

I have tried implementing the GCD way of factoring p(x) with (x^7+x+1) to get to a commond divisor, but that common divisor looks too huge to bt eright, this is what I am getting at the moment:
1-((-32x^2/5)+(208x/25)-(632/125))

2. first thing, you wrote $(\mathbb{F}_2)^8 = F_2 [x] / p(x)$. this is not correct because $(\mathbb{F}_2)^8$ is not a field. for example, (1,1,1,1,1,1,1,1) is the unit in this ring, but then there is no inverse for (0,0,0,0,0,0,0,1).

when you want to find the inverse for an element f(x) in a field $\mathbb{F}[x]/p(x)$ where F is a field and p(x) irreducible you use the euclidean algorithm to find the h(x)=gcd(f(x),p(x)) and the a(x), b(x) that satisfy a(x)p(x)+b(x)f(x) = h(x). because p is irreducible you must have h(x) is invertible so $h^{-1} b f = h^{-1} (h - a p) = 1 - h^{-1}a p = 1 (mod\; p(x) )$

$(x^8+x^4+x^3+x+1) = (x^7+x+1) x + (x^4+x^3+x^2+1)$
$(x^7+x+1) = (x^4+x^3+x^2+1) (x^3+x^2+1) + ( x )$
$(x^4+x^3+x^2+1) = (x) (x^3+x^2+x) + 1$
some rearranging ...
$1 = (x^4+x^3+x^2+1) - (x) (x^3+x^2+x)$
$= (x^4+x^3+x^2+1) - [f(x) - (x^4+x^3+x^2+1) (x^3+x^2+1)](x^3+x^2+x)$
$=(x^4 + x^3 + x^2 + 1) [ 1 + (x^3 + x^2 + 1) ( x^3 + x^2 + x ) ] - f(x)( x^3 + x^2 + x )$
$= (x^4+x^3+x^2+1) (x^6+x^2+x+1) - f(x)(x^3+x^2+x)$
$=(p(x)-x f(x)) (x^6+x^2+x+1) - f(x)(x^3+x^2+x)$
$=p(x)(x^6+x^2+x+1) - f(x)[(x^3+x^2+x)-x(x^6+x^2+x+1)]$
$=p(x)(x^6+x^2+x+1) - f(x)(x^7)$

so the inverse of f(x) = x^7+x+1 is x^7. (notice that because the field is F2 minus and plus are the same.)

3. Originally Posted by cha0s4u
Write down an analogue of the extended Euclidean Algorithm for the ring F2^[x]. Given that p(x) = x^8 + x^4 + x^3 + x + 1 is a (primitive) irreducible polynomial. Find the inverse of x^7 + x + 1 in the field F2^8 = F2^[x]/(p(x)).

I have tried implementing the GCD way of factoring p(x) with (x^7+x+1) to get to a common divisor, but that common divisor looks too huge to be right, this is what I am getting at the moment:
1-((-32x^2/5)+(208x/25)-(632/125))
If I understand the notation correctly, the ground field here is meant to be $\mathbb{F}_2$, the field with two elements. That means that the coefficients in the polynomials can only be 0 or 1, with the rule that 1+1=0. So you should not be getting coefficients like 632/125.

To start you off on the right lines, the first step in the euclidean algorithm is to divide p(x) by x^7+x+1, like so:

$x^8 + x^4 + x^3 + x + 1 = (x^7+x+1)x + x^4+x^3+x^2+1.$

Next, you divide x^7+x+1 by that remainder:

$x^7+x+1 = (x^4+x^3+x^2+1)(x^3+x^2+1) + x$,

and so on until you get the remainder 1. Then work backwards to find 1 as a multiple of x^7+x+1 plus a multiple of p(x).

[My answer for the inverse of x^7+x+1 in $\mathbb{F}_2[x]/(p(x))$ is that it is x^7.]

Edit. Prometheus beat me to it!

4. Thank you Prometheus and Opalg!

I scrutinized with what i had done earlier, and it seems the trouble started in the very beginning (1st step of factorization); I get:
$
(x^8+x^4+x^3+x+1) = (x^7+x+1) x + (x^4+x^3-x^2+1)
$

And you guys get:
$
(x^8+x^4+x^3+x+1) = (x^7+x+1) x + (x^4+x^3+x^2+1)
$

In my case, I can verify that both sides are equal, but not in your case, it seems instead of (x^4+x^3+x^2+1) it should have been (x^4+x^3-x^2+1)
(minus x^2)

Am I doing something wrong or is it in your case, because I did the exact similar process of implementing Extended Euclid's algo. But I get that very big value... Can you please help me understand what I am doing wrong, or how should it be?

Thanks!

5. Makes no difference. In the field with two elements, 1+1=0. Therefore -1 is the same as +1, and $x^4+x^3-x^2+1$ is the same as $x^4+x^3+x^2+1$.

6. Thank You Opalg!

I think, I need to get my basics right... Thanks for the great help! and the tip

Thanks!