Complexities of normal bases constructed from Gauss periods

Let q be a power of a prime p, and let (r=nk+1) be a prime such that (rnot mid q), where n and k are positive integers. Under a simple condition on q, r and k, a Gauss period of type (n, k) is a normal element of ({mathbb {F}}_{q}^{n}) over ({mathbb {F}}_q); the complexity of the resulting normal basis of ({mathbb {F}}_{q}^{n}) over ({mathbb {F}}_q) is denoted by C(n, k; p). Recent works determined C(n, k; p) for (kle 7) and all qualified n and q. In this paper, we show that for any given (k>0), C(n, k; p) is given by an explicit formula except for finitely many primes (r=nk+1) and the exceptional primes are easily determined. Moreover, we describe an algorithm that allows one to compute C(n, k; p) for the exceptional primes (r=nk+1). Our numerical results cover C(n, k; p) for (kle 20) and all qualified n and q.