Gauss periods and fast exponentiation in finite fields: Extended abstract
Gauss periods can be used to implement finite field arithmetic efficiently. For a small prime p and infinitely many integers n, exponentiation of an arbitrary element in Fp ncan be done with O(n 2 loglog n) operations in Fp, and exponentiation of a Gauss period with O(n 2) operations in Fp. Comparing to the previous estimate O(n 2 log nloglog n), using polynomial bases, this shows that normal bases generated by Gauss periods offer some asymptotic computational advantage. Experimental results indicate that Gauss periods are often primitive elements in finite fields.
|Series||Lecture Notes in Computer Science|
Gao, S. (Shuhong), Gathen, J.Z. (Joachim Von Zur), & Panario, D. (1995). Gauss periods and fast exponentiation in finite fields: Extended abstract. In Lecture Notes in Computer Science.