Computing special powers in finite fields
Joachim von zur Gathen, Michael Nöcker · Mathematics of Computation · 2003
We study exponentiation in nonprime finite fields with very special exponents such as they occur, for example, in inversion, primitivity tests, and polynomial factorization. Our algorithmic approach improves the corresponding exponentiation problem from about quadratic to about linear time.