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

Vol. 18, No. 6, pp. 3-16, Oct. 2008
10.13089/JKIISC.2008.18.6.3, Full Text:
Keywords: square roots, Finite fields, Tonelli-Shanks algorithm
Abstract

In this paper we study exponentiation in finite fields $F{_p}{^{k}}$(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 $F{_p}{^{k}}$. 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 $p{\equiv}1$ (mod 16). Several numerical examples are given that show the speed-up of the proposed methods.

Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
D. Han, D. Choi, H. Kim, J. Lim, "Efficient Computation of Square Roots in Finite Fields $F{_p}{^{k}}$," Journal of The Korea Institute of Information Security and Cryptology, vol. 18, no. 6, pp. 3-16, 2008. DOI: 10.13089/JKIISC.2008.18.6.3.

[ACM Style]
Dong-Guk Han, Doo-Ho Choi, Ho-Won Kim, and Jong-In Lim. 2008. Efficient Computation of Square Roots in Finite Fields $F{_p}{^{k}}$. Journal of The Korea Institute of Information Security and Cryptology, 18, 6, (2008), 3-16. DOI: 10.13089/JKIISC.2008.18.6.3.