Efficient computation of traces of all primitive elements in field extensions of GF(2)
It's straightforward to solve this problem in time $\phi(2^n-1)$ field operations, and there's no hope to do significantly better than this.

Computing the trace of a single element can be done in $n$ field operations (just by applying the definition).  So, we can simply compute the trace for each of the $\phi(2^n-1)/n$ elements with distinct trace.  The running time will be $n \times \phi(2^n-1)/n = \phi(2^n-1)$.

There is no hope to do significantly better than this.  There are $\phi(2^n-1)$ primitive elements in the field.  If you want an algorithm to output the trace of all of those values, the length of the output from the algorithm has to be at least $\phi(2^n-1)$.  It follows that the running time of any such algorithm has to be at least $\Theta(\phi(2^n-1))$.  So, you can't do asymptotically better than the straightforward algorithm.

Finally let me point out that $\phi(2^n-1)$ is exponentially large in $n$ (in general).  This means that any algorithm for your problem will have running time that is exponential in $n$.  This means that no algorithm can possibly be efficient for anything except very small values of $n$.