Let n >1 and let F2 n be the finite field with 2 n elements. The trace function

Question

Let n>1 and let F2n be the finite field with 2n elements. The trace function T(x)=x+x2+x22+?+x2n?1 is an onto linear transformation from F2n to F2. There are ?(2n?1) primitive elements in F2n (generators of the cyclic multiplicative subgroup of the field) where ? is Euler's totient function.

I am interested in computing the traces of all the primitive elements in F2n efficiently. Note that all the primitive elements are given by ?k where ? is one of the primitive elements, and gcd(k,2n?1)=1. Moreover two primitive elements ?k, ?s have the same trace if and only if k?s?2i(mod2n?1) for some i with 0?i?n?1. This means we need to compute ?(2n?1)/n traces.

Is there an efficient algorithm to do this?

Explanation / Answer

It's straightforward to solve this problem in time ?(2n?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 ?(2n?1)/n elements with distinct trace. The running time will be n

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.