BROWSE
Detail
Journal Article
Improved Computation of Square Roots in Specific Finite Fields
Cited 15 time in 
Share 
Share
- Authors
- Dong-Guk Han, Doo Ho Choi, Ho Won Kim
- Issue Date
- 2009-02
- Citation
- IEEE Transactions on Computers, v.58, no.2, pp.188-196
- ISSN
- 0018-9340
- Publisher
- IEEE
- Language
- English
- Type
- Journal Article
- Abstract
- In this paper, we study exponentiation in the specific finite fields F q 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. © 2006 IEEE.
- KSP Keywords
- Algorithmic approach, Finite fields, Numerical examples, Square root