Efficient Computation of Square Roots in Finite Fields $F{_p}{^{k}}$

In this paper we study exponentiation in finite fields (k is odd) with very special exponents such as they occur in algorithms for computing square roots. Our algorithmic approach improves the corresponding exponentiation independent of the characteristic of . To the best of our knowledge, it is the first major improvement to the Tonelli-Shanks algorithm, for example, the number of multiplications can be reduced to at least 60% on average when (mod 16). Several numerical examples are given that show the speed-up of the proposed methods.