Improved Computation of Square Roots in Specific Finite Fields

Abstract

In this paper, we study exponentiation in the specific finite fields F, with very special exponents such as those that occur in algorithms for computing square roots. Here, q is a prime power, q = p <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> , where k > 1, and k is odd. Our algorithmic approach improves the corresponding exponentiation resulted from the better rewritten exponent. 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 percent on the average when p= 1 (mod 16). Several numerical examples are given that show the speedup of the proposed methods.