Joachim von zur Gathen, Shuhong Gao
Gauss periods, primitive normal bases and fast exponentiation in finite fields

MSC:

00-01 Instructional exposition (textbooks, tutorial papers, etc.)

Abstract: Gauss periods can be used to implement arithmetic in finite fields efficiently
and to construct primitive (self-dual) normal bases. With these methods, exponentiation
of an arbitrary element in F can be done with O(n^2loglogn) operations in F, and
exponentiation of an Gauss period with O(n^2) operations in F, for a small prime power q
and infinitly many integers n. Experimental results indicate that Gaus periods almost
always have high multiplicative order and are frequently (more than half the time) prim-
itive elements over F2. In fact, for every n <=527 not divisible by 8, we find a primitive
Gauss period in F2n over F2. Thus Gauss periods in finite fields generate many primitive
(self-dual) normal bases