Galois Field

Quick math question:
I'm working with galois fields and I'd like to know if a polynom such as a(x)=x in CG(2^3) and mod p(x)=x^2 + x + 1. What is the inverse of a(x) (aka a(x)^-1)?

-x-1

I know a lot about this, but I cannot understand what your question is.  If you mod by x^2+x+1, you get GF(2^2).  To get GF(2^3) you need to mod by x^3+x+1 or by x^3+x^2+1.

If you consider GF(2^3) = Z_2[x] / <x^3 + x + 1>, then x^(-1) = x^2 + 1, because x * (x^2 + 1) = x^3 + x = (x + 1) + x = 1. 

But if you consider GF(2^3) = Z_2[x] / <x^3 + x^2 + 1>, then x^(-1) = x^2 + x, because x * (x^2 + x) = x^3 + x^2 = (x^2 + 1) + x^2 = 1. 

I hope that made some sense.

Perhaps it is also worth pointing out that in GF(p^n), every element a has a^(p^n) = a.  This means that for any element a you have a^(-1) = a^(p^n-2).  Calculating a^(p^n-2) is straightforward, requiring no more than about n log_2(p) multiplications.

For example, let's consider GF(2^3) = Z_2[x] / <x^3 + x + 1>, and try to calculate x^(-1).  Since x^8 = x, we want to calculate x^(8-2) = x^6.  x^3 = x + 1, and x^6 = (x^3)^2 = (x+1)^2 = x^2 + 1, which is the answer.

You are awesome ID:SClMoOXK
This is the answer I was looking for (specially the second paragraph). I had a similar explanation on my notes but some of the stuff you explained was left out.
Thanks again.

Hey, I'm glad I could help.

I'm also glad my wild guess at what you wanted turned out to be right.