<s>[INST] Calculate the trace of all elements in $F_8$ I got the following exercise where you have to calc the trace of all elements in ${F_8}$ which is constructed as ${F_2}[x]$/(${x^3+x+1}$)${F_2}[x]$.
Up to now I did those steps:
1) Find all elements in ${F_8}$ which are in my opinion: $0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1$
2) Then I found those traces for the elements:
$Tr(0)=0\\
Tr(1)=1\\
Tr(x)=x+x^2+x^4\\
Tr(x+1)=Tr(x)+Tr(1)=x^4+x^2+x+1\\
Tr(x^2)=x^8+x^4+x^2 \text{(must this be reduced!?)}\\
Tr(x^2+1)=Tr(x^2)+Tr(1)=x^8+x^4+x^2+1\\
Tr(x^2+x)=Tr(x^2)+Tr(x)=x^8+x\\
Tr(x^2+x+1)=Tr(x^2)+Tr(x)+Tr(1)=x^8+x+1$
Is this procedure correct? Thank you!
 [/INST] You can take advantage of the linearity of trace. To make the notation less cumbersome I denote the coset $x+\langle x^3+x+1\rangle$ by $\alpha$. In that case the elements of the field are
$$
\Bbb{F}_8=\{a_0+a_1\alpha+a_2\alpha^2\mid a_0,a_1,a_2\in\Bbb{F}_2\}.
$$
The minimal polynomial of $\alpha$ is $m(x)=x^3+x+1$. Its other zeros are the conjugates $\alpha^2$ and $\alpha^4=\alpha\cdot\alpha^3=\alpha(\alpha+1)$. Therefore
$$
\begin{aligned}
m(x)&=(x-\alpha)(x-\alpha^2)(x-\alpha^4)=x^3-(\alpha+\alpha^2+\alpha^4)x^2+\cdots\\
&=x^3-tr(\alpha)x^2+\cdots
\end{aligned}
$$
Therefore we can conclude that $tr(\alpha)=0$. This also follows from the earlier calculation (that also appears in Timbuc's answer) giving us that $\alpha^4=\alpha+\alpha^2$.
Because $m(x)$ is also a minimal polynomial of $\alpha^2$, we see that $tr(\alpha^2)=tr(\alpha)$, so also $tr(\alpha^2)=0$. Clearly
$$
tr(1)=1+1^2+1^4=3=1.
$$
Linearity thus gives us that
$$
tr(a_0+a_1\alpha+a_2\alpha^2)=a_0\, tr(1)+a_1\, tr(\alpha)+a_2\, tr(\alpha^2)=a_0.
$$
</s>