Results 1 to 6 of 6

Thread: 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
    10
    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
    10
    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, 07:27 AM
  2. GCD and extended euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Dec 11th 2010, 05:25 AM
  3. Extended euclidean algorighm question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Oct 4th 2009, 10:16 AM
  4. Extended Euclidean algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 21st 2009, 01:24 PM
  5. Replies: 6
    Last Post: Mar 31st 2009, 05:44 PM

Search Tags


/mathhelpforum @mathhelpforum