Algorithms for exponentiation in finite fields

Gauss periods yield (self-dual) normal bases in finite fields, and these no rmal bases can be used to implement arithmetic efficiently. It is shown tha t for a small prime power q and infinitely many integers n, multiplication in a normal basis of F(q)n over F-q can be computed with O(n log n loglog n ), division with O(n log(2) n loglog n) operations in F-q: and exponentiati on of an arbitrary element in F(q)n with O(n(2) loglog n) operations in F-q . We also prove that using a polynomial basis exponentiation in F(2)n can b e done with the same number of operations in F-2 for all n. The previous be st estimates were O(n(2)) for multiplication in a normal basis, and O(n(2) log n log log n) for exponentiation in a polynomial basis. (C) 2000 Academi c Press.