Normal bases via general Gauss periods
Sandra Feisel, Joachim von zur Gathen, M. Shokrollahi · Mathematics of Computation · 1999
Gauss periods have been used successfully as a tool for constructing normal bases in finite fields. Starting from a primitive r r th root of unity, one obtains under certain conditions a normal basis for F q n \mathbb {F}_{q^n} over F q \mathbb {F}_q , where r r is a prime and n k = r − 1 nk=r-1 for some integer k k . We generalize this construction by allowing arbitrary integers r r with n k = φ ( r ) nk=\varphi (r) , and find in many cases smaller values of k k than is possible with the previously known approach.