A Complete Generalization of Atkin's Square Root Algorithm

• Autorzy: Rotaru A. S. , Iftene S.
• Języki publikacji: EN

Abstrakty

EN

Atkin's algorithm [2] for computing square roots in Z*_p, where p is a prime such that p ≡ 5 mod 8, has been extended by Müller [15] for the case p ≡ 9 mod 16. In this paper we extend Atkin's algorithm to the general case p ≡ 2^s + 1 mod 2^s+1, for any s ≥2, thus providing a complete solution for the case p ≡ 1 mod 4. Complexity analysis and comparisons with other methods are also provided.

Słowa kluczowe

EN

complexity; efficient computation; square roots

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 125, nr 1
• Strony: 71--94
• Opis fizyczny: Bibliogr. 22 poz., tab., wykr.

Twórcy

autor

Rotaru A. S.

• Institute of Computer Science, Romanian Academy, Carol I no. 8, 700505 Iasi, Romania

autor

Iftene S.

• Department of Computer Science, Alexandru Ioan Cuza University, General Berthelot no. 16, 700483 Iasi, Romania

Bibliografia

• [1] Ankeny, N. C.: The Least Quadratic Non Residue, Annals of Mathematics, 55(1), 1952,65-72.
• [2] Atkin, A.: Probabilistic primality testing (summary by F. Morain), Technical Report 1779, INRIA, 1992, URL: http ://algo. inria.fr/seminars/sem91 -92/atkin.pdf.
• [3] Atkin, A., Morain, F.: Elliptic Curves and Primality Proving, Mathematics of Computation, 61(203), 1993, 29-68.
• [4] Bach, E., Shallit, J.: Algorithmic Number Theory, Volume I: Efficient Algorithms, MIT Press, 1996.
• [5] Bernstein, D. J.: Faster square roots in annoying finite fields (preprint), 2001, URL: http ://cr.yp.to/papers/sqroot.pdf.
• [6] Cipolla, M.: Un metodo per la risoluzione della congruenza di secondo grado, Rendiconto dell'Accademia delle Scienze Fisiche e Matematiche, Napoli, 9, 1903, 154-163.
• [7] Crandall, R., Pomerance, C.: Prime Numbers. A Computational Perspective, Springer-Verlag, 2001.
• [8] Eikenberry, S., Sorenson, J.: Efficient Algorithms for Computing the Jacobi Symbol, Journal of Symbolic Computation, 26(4), 1998, 509-523.
• [9] Han, D.-G., Choi, D., Kim, H.: Improved Computation of Square Roots in Specific Finite Fields, IEEE Transactions on Computers, 58(2), 2009, 188-196.
• [10] IEEE Std 2000-1363. Standard Specifications For Public-Key Cryptography, 2000.
• [11] Kong, F., Cai, Z., Yu, J., Li, D.: Improved generalized Atkin algorithm for computing square roots in finite fields, Information Processing Letters, 98(1), 2006, 1-5.
• [12] Lehmer, D.: Computer technology applied to the theory of numbers, Studies in number theory (W. Leveque, Ed.), 6, Prentice-Hall, 1969.
• [13] Lemmermeyer, F.: Reciprocity Laws. From Euler to Eisenstein, Springer-Verlag, 2000.
• [14] Lindhurst, S.: An analysis of Shanks’s algorithm for computing square roots in finite fields, in: Number theory (R.Gupta, K. Williams, Eds.), American Mathematical Society, 1999,231-242.
• [15] Muller, S.: On the Computation of Square Roots in Finite Fields, Designs, Codes and Cryptography, 31(3), 2004,301-312.
• [16] Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Transactions on Information Theory, 24, 1978, 106-110.
• [17] Pomerance, C.: The Quadratic Sieve Factoring Algorithm, Advances in Cryptology: Proceedings ofEURO- CRYPT84 (T. Beth, N. Cot, I. Ingemarsson, Eds.), 209, Springer-Verlag, 1985.
• [18] Postl, H.: Fast evaluation of Dickson Polynomials, in: Contributions to General Algebra (D. Dorninger, G. Eigenthaler, H. Kaiser, W. Muller, Eds.), vol. 6, B.G. Teubner, 1988, 223-225.
• [19] Schoof, R.: Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p, Mathematics of Computation, 44(170), 1985, 483-494.
• [20] Shanks, D.: Five number-theoretic algorithms, Proceedings of the second Manitoba conference on numerical mathematics (R. Thomas, H. Williams, Eds.), 7, Utilitas Mathematica, 1973.
• [21] Sze, T.-W.: On taking square roots without quadratic nonresidues over finite fields, Mathematics of Computation, 80(275), 2011,1797-1811, (a preliminary version of this paper has appeared as arXiv e-print, available at http://arxiv.org/abs/0812.2591v3).
• [22] Tonelli, A.: Bemerkunguber die Auflosung quadratischer Congruenzen, Gottinger Nachrichten, 1891, 344346.