The ﬁeld GF(8) of 8 elements can be thought of as consisting of elements of the form a*x^2 + bx + c, where a, b, c ∈ Z2.

(Thus, all coeﬃcients are simpliﬁed mod 2.)

Moreover, x^3 = x + 1.

(a) Compute (x^2 + x + 1) + (x^2 + 1), simplifying your answer to the form a*x^2 + bx + c for a, b, c ∈ Z2.

(b) Compute (x^2 + 1) * (x + 1), simplifying your answer to the form a*x^2 + bx + c for a, b, c ∈ Z2.

(c) Show that x is a primitive root by computing the powers x^k for k = 3,4, . . .7, simplifying your answers to the form a*x^2 + bx + c for a, b, c ∈ Z2. (This shows that <x> is cyclic of order 7.)

(d) Compute (x^2 + 1)−1, simplifying your answer to the form a*x^2 + bx + c for a, b, c ∈ Z2. (Hint: Use the result of (c) to represent x^2 + 1 as a power of x. Then simplify (x^2 + 1)−1 using rules for powers, then look up the answer using the computation you did in (c).)

Remark. You can use the ax2 + bx + c to add elements of GF(8), because it’s just a matter of adding coeﬃcients and reducing mod 2. On the other hand, you can multiply elements by representing them as powers of x and using rules for powers, translating back to ax2 + bx + c by using (c) if needed.

This is what I have so far:

(a) (x^2 + x + 1) + (x^2 + 1) = 2x^2 + x + 2 = x

(b) (x^2 + 1) * (x + 1) = x^3 + x^2 + x + 1 = (x + 1) + x^2 + x + 1 = x^2 + 2x + 2 = x^2

Then for part (c) I get lost about how to show that x is a primitive root.