Results 1 to 6 of 6

Math Help - Extended Euclidean related polynomial's inverse

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    3

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

    Please suggest...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    May 2008
    Posts
    33
    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) )

    in your case we have
    (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.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by cha0s4u View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    Posts
    3

    Question

    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:
    <br />
(x^8+x^4+x^3+x+1) = (x^7+x+1) x + (x^4+x^3-x^2+1)<br />

    And you guys get:
    <br />
(x^8+x^4+x^3+x+1) = (x^7+x+1) x + (x^4+x^3+x^2+1)<br />

    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2008
    Posts
    3
    Thank You Opalg!

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

    Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Extended Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 17th 2011, 08:27 AM
  2. GCD and extended euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: December 11th 2010, 06:25 AM
  3. Extended euclidean algorighm question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 4th 2009, 11:16 AM
  4. Extended Euclidean algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 21st 2009, 02:24 PM
  5. Replies: 6
    Last Post: March 31st 2009, 06:44 PM

Search Tags


/mathhelpforum @mathhelpforum