Let $n > 1$ and let $\mathbb{F}_{2^n}$ be the finite field with $2^n$ elements. The trace function $T(x) = x + x^2 + x^{2^2} + \cdots + x^{2^{n-1}}$ is an onto linear transformation from $\mathbb{F}_{2^n}$ to $\mathbb{F}_2$. There are $\phi(2^n-1)$ primitive elements in $\mathbb{F}_{2^n}$ (generators of the cyclic multiplicative subgroup of the field) where $\phi$ is Euler's totient function.

I am interested in computing the traces of all the primitive elements in $\mathbb{F}_{2^n}$ efficiently. Note that all the primitive elements are given by $\alpha^k$ where $\alpha$ is one of the primitive elements, and $\gcd(k, 2^n-1) = 1$. Moreover two primitive elements $\alpha^k$, $\alpha^s$ have the same trace if and only if $k \equiv s\cdot 2^i \pmod{2^n-1}$ for some $i$ with $0 \leq i \leq n-1$. This means we need to compute $\phi(2^n-1)/n$ traces.

Is there an efficient algorithm to do this?

  • $\begingroup$ Can you clarify what you mean by efficient? What running time would qualify as efficient? Also, what have you tried or considered? $\endgroup$ – D.W. Mar 22 '15 at 4:55

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.