Algorithms for Exponentiation in Finite
β
Shuhong Gao; Joachim Von zur gathen; Daniel Panario; Victor Shoup
π
Article
π
2000
π
Elsevier Science
π
English
β 298 KB
Gauss periods yield (self-dual) normal bases in finite fields, and these normal bases can be used to implement arithmetic efficiently. It is shown that for a small prime power q and infinitely many integers n, multiplication in a normal basis of F q n over Fq can be computed with O(n log n loglog n)