Improved generalized Atkin algorithm for computing square roots in finite fields. (English) Zbl 1195.11166
Summary: Recently, S. Müller [Des. Codes Cryptography 31, No. 3, 301–312 (2004; Zbl 1052.11084)] developed a generalized Atkin algorithm for computing square roots, which requires two exponentiations in finite fields \(\text{GF}(q)\) when \(q\equiv 9\pmod{16}\). In this paper, we present a simple improvement to it and the improved algorithm requires only one exponentiation for half of squares in finite fields \(\text{GF}(q)\) when \(q \equiv 9\pmod{16}\). Furthermore, in finite fields \(\text{GF}(p^m)\), where \(p\equiv 9\pmod{16}\) and \(m\) is odd, we reduce the complexity of the algorithm from \(O(m^{3}\log^3 p)\) to \(O(m^2\log^2 p(\log m+\log p))\) using the Frobenius map and normal basis representation.
MSC:
| 11Y16 | Number-theoretic algorithms; complexity |
| 68W40 | Analysis of algorithms |
| 11T99 | Finite fields and commutative rings (number-theoretic aspects) |
| 94A60 | Cryptography |
Citations:
Zbl 1052.11084References:
| [1] | IEEE Std 2000-1363, Standard Specifications for Public Key Cryptography, 2000; IEEE Std 2000-1363, Standard Specifications for Public Key Cryptography, 2000 |
| [2] | Cohen, H., A Course in Computational Algebraic Number Theory (1993), Springer-Verlag: Springer-Verlag Berlin · Zbl 0786.11071 |
| [3] | Atkin, A. O.L., Probabilistic primality testing, Summary by F. Morain, INRIA Res. Rep., 1779, 159-163 (1992) |
| [4] | Lindhurst, S., An analysis of Shanks’s algorithm for computing square roots in finite fields, (CRM Proc. Lecture Notes, vol. 19 (1999), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 231-242 · Zbl 0928.11055 |
| [5] | Crandall, R.; Pomerance, C., Prime Numbers. A Computational Perspective (2001), Springer-Verlag: Springer-Verlag New York |
| [6] | Barreto, P. S.L. M.; Kim, H. Y.; Lynn, B.; Scott, M., Efficient algorithms for pairing-based cryptosystems, (Advances in Cryptology—CRYPTO 2002. Advances in Cryptology—CRYPTO 2002, Lecture Notes in Comput. Sci., vol. 2442 (2002), Springer-Verlag: Springer-Verlag Berlin), 354-368 · Zbl 1026.94520 |
| [7] | Müller, S., On the computation of square roots in finite fields, Des. Codes Cryptogr., 31, 2, 301-312 (2004) · Zbl 1052.11084 |
| [8] | Lidl, R.; Niederreiter, H., Finite Fields, Encyclopedia of Mathematics and Its Applications, vol. 20 (1997), Cambridge University Press: Cambridge University Press Cambridge |
| [9] | Itoh, T.; Tsujii, S., A fast algorithm for computing multiplicative inverses in \(GF(2^m)\) using normal bases, Inform. and Comput., 78, 171-177 (1988) · Zbl 0672.68015 |
| [10] | Bach, E., A note on square roots in finite fields, IEEE Trans. Inform. Theory, 36, 6, 1494-1498 (1990) · Zbl 0718.11066 |
| [11] | von zur Gathen, J.; Nöcker, M., Computing special powers in finite fields, Math. Comput., 73, 247, 1499-1523 (2004) · Zbl 1081.68125 |
| [12] | Gordon, D. M., A survey of fast exponentiation methods, J. Algorithms, 27, 129-146 (1998) · Zbl 0915.11064 |
| [13] | Schoof, R., Counting points on elliptic curves over finite fields, J. Theor. Nombres Bordeaux, 7, 219-254 (1995) · Zbl 0852.11073 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
