Results 1 to 3 of 3

Math Help - Galois Field Division Check

  1. #1
    Newbie
    Joined
    Mar 2012
    From
    USA
    Posts
    1

    Galois Field Division Check

    Hello. I worked through a Galois field problem and I just wanted to see if I have done everything correctly.
    The question follows,

    Compute in GF(2^8):
    (x^4 + x + 1)/(x^7 + x^6 + x^3 + x^2)
    where the irreducible polynomial is P(x) = x^8 + x^4 + x^3 + x + 1.

    The first thing I did was find the inverse of (x^7 + x^6 + x^3 + x^2) which equals (x^4 + x^3 + x + 1).

    Then, I did (x^4 + x + 1)*(x^4 + x^3 + x + 1)

    =x^8 + x^7 + x^5 + x^4 + x^4 + x^2 + x + x^4 + x^3 + x + 1
    =x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + 1

    I declared x^8 = x^7 + x^5 + x^4 mod P(x)

    I plugged this into the result I have.

    =(x^7 + x^5 + x^4) + x^7 + x^5 + x^4 + x^3 + x^2 + 1
    =x^3 + x^2 + 1 (Final Answer)

    Can anyone just check my work to see if I have done everything correctly? If I am wrong, I am not looking for the actual answer, but maybe if you can point out the section where I did something wrong would suffice. Thank you very much in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    913
    Thanks
    205

    Re: Galois Field Division Check

    If you did it correctly, you should have (x^7 + x^6 + x^3 + x^2)*(x^3 + x^2 + 1) = (x^4 + x + 1).

    (x^7 + x^6 + x^3 + x^2)*(x^3 + x^2 + 1) =
    (x^10 + x^9 + x^6 + x^5)+(x^9 + x^8 + x^5 + x^4)+(x^7 + x^6 + x^3 + x^2) =
    x^10 + x^8 + x^7 + x^4 + x^3 + x^2 =
    x^8 + x^7 + x^6 + x^5 + x^4 =
    x^7 + x^6 + x^5 + x^3 + x + 1

    which is not x^4 + x + 1.

    I get (x^4 + x + 1)*(x^4 + x^3 + x + 1) =
    (x^8 + x^7 + x^5 + x^4)+(x^5 + x^4 + x^2 + x)+(x^4 + x^3 + x + 1) =
    x^8 + x^7 + x^4 + x^3 + x^2 + 1 =
    x^7 + x^2 + x

    Which is the correct answer, since:
    (x^7 + x^6 + x^3 + x^2)*(x^7 + x^2 + x) =
    (x^14 + x^13 + x^10 + x^9)+(x^9 + x^8 + x^5 + x^4)+(x^8 + x^7 + x^4 + x^3) =
    x^14 + x^13 + x^10 + x^7 + x^5 + x^3 =
    x^13 + x^9 + x^6 + x^5 + x^3 =
    x^8 + x^3 =
    x^4 + x + 1

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,154
    Thanks
    595

    Re: Galois Field Division Check

    Quote Originally Posted by taskforce141 View Post
    Hello. I worked through a Galois field problem and I just wanted to see if I have done everything correctly.
    The question follows,

    Compute in GF(2^8):
    (x^4 + x + 1)/(x^7 + x^6 + x^3 + x^2)
    where the irreducible polynomial is P(x) = x^8 + x^4 + x^3 + x + 1.

    The first thing I did was find the inverse of (x^7 + x^6 + x^3 + x^2) which equals (x^4 + x^3 + x + 1).

    Then, I did (x^4 + x + 1)*(x^4 + x^3 + x + 1)
    you are fine up to here.

    =x^8 + x^7 + x^5 + x^4 + x^5 + x^4 + x^2 + x + x^4 + x^3 + x + 1
    =x^8 + x^7 + ( ) + x^4 + x^3 + x^2 + 1
    corrections noted in red.

    I declared x^8 = x^7 + x^5 + x^4 mod P(x)
    this is entirely wrong. x^8 = x^4 + x^3 + x + 1 mod P(x), since x^8 - x^4 - x^3 - x - 1 = x^8 + x^4 + x^3 + x + 1 is in <P(x)> (being P(x) itself).

    I plugged this into the result I have.

    =(x^7 + x^5 + x^4) + x^7 + x^5 + x^4 + x^3 + x^2 + 1
    =x^3 + x^2 + 1 (Final Answer)

    Can anyone just check my work to see if I have done everything correctly? If I am wrong, I am not looking for the actual answer, but maybe if you can point out the section where I did something wrong would suffice. Thank you very much in advance.
    i arrive at an answer of x^7 + x^2 + x, as did hollywood.
    Last edited by Deveno; March 29th 2012 at 12:32 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Ring, field, Galois-Field, Vector Space
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 15th 2012, 03:25 PM
  2. Inverse in Galois field
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 19th 2011, 11:42 PM
  3. splitting field and galois groups
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: May 13th 2010, 08:24 PM
  4. Doubt in Galois Field
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 17th 2009, 08:37 PM
  5. what is the advantage of galois field
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 22nd 2008, 08:50 AM

Search Tags


/mathhelpforum @mathhelpforum