Title :
Improved Computation of Square Roots in Specific Finite Fields
Author :
Han, Dong-Guk ; Choi, Dooho ; Kim, Howon
Author_Institution :
Electron. & Telecommun. Res. Inst., Daejeon
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 = pk, 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.
Keywords :
computational complexity; cryptography; number theory; Tonelli-Shanks algorithm; computational number theory; cryptography; prime power; specific finite fields; square root extraction; Costs; Digital arithmetic; Elliptic curve cryptography; Elliptic curves; Galois fields; Helium; Periodic structures; Telecommunication computing; Algorithms; Cost/performance; Square roots; cryptography.; efficient computation; finite fields;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2008.201