patternMinor
Efficient computation of traces of all primitive elements in field extensions of GF(2)
Viewed 0 times
fieldcomputationallelementsextensionsefficientprimitivetraces
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#40625, answer score: 2
Revisions (0)
No revisions yet.