Thread: 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.

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

Originally Posted by taskforce141

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.