On the Pocklington-Peralta square root algorithm in finite fields
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
We present a new square root algorithm in finite fields which is a variant of the Pocklington-Peralta algorithm. We give the complexity of the proposed algorithm in terms of the number of operations (multiplications) in finite fields, and compare the result with other square root algorithms, the Tonelli-Shanks algorithm, the Cipolla-Lehmer algorithm, and the original Pocklington-Peralta square root algorithm. Both the theoretical estimation and the implementation result imply that our proposed algorithm performs favorably over other existing algorithms. In particular, for the NIST suggested field P-224, we show that our proposed algorithm is significantly faster than other proposed algorithms.
Abstract
We present a new square root algorithm in finite fields which is a variant of the Pocklington-Peralta algorithm. We give the complexity of the proposed algorithm in terms of the number of operations (multiplications) in finite fields, and compare the result with other square root algorithms, the Tonelli-Shanks algorithm, the Cipolla-Lehmer algorithm, and the original Pocklington-Peralta square root algorithm. Both the theoretical estimation and the implementation result imply that our proposed algorithm performs favorably over other existing algorithms. In particular, for the NIST suggested field P-224, we show that our proposed algorithm is significantly faster than other proposed algorithms.
참고문헌 (14)
- "Faster square roots in annoying finite fields"[URL]
- M. Cipolla, "Un metodo per la risolutione della congruenza di secondo grado", Rendiconto dell’Accademia Scienze Fisiche e Matematiche, Napoli, Ser, 3, pp.154~163 (1903)
- Federal information processing standards publication 186–4, "Digital Signature Standard", Information Technology Laboratory, National Institute of Standards and Technology, 186~184 (2013)
- N. Koo, "Square root algorithm in Fq for q ≡ 2s+1(mod 2s+1)", Electronics Letters, 49(7), pp.467~468 (2013)[DOI]
- N. Koo, "On r-th root extraction algorithm in Fq for q ≡ lrs +1(mod r s+1)with 0 < ` < r and small s", IEEE Trans. Comput, 65(1), pp.322~325 (2016)[DOI]
- D. H. Lehmer, "Computer technology applied to the theory of numbers, in Studies in Number Theory", pp.117~151 (1969), Math. Assoc. America
- Scott Lindhurst, "An analysis of Shanks’s algorithm for computing square roots in finite fields", CRM Proceedings and Lecture Notes, pp.231~242 (1999), American Mathematical Society[DOI]
- Siguna Müller, "On the Computation of Square Roots in Finite Fields", Designs, Codes and Cryptography, 31(3), pp.301~312 (2004), Springer Science and Business Media LLC[DOI]
- I. Niven, "An Introduction to the Theory of Numbers" (1991), John Wiley & Sons, Inc
- R. C. Peralta, "A simple and fast probabilistic algorithm for computing square roots modulo a prime number", IEEE Trans. Inform. Theory, 32(6), pp.846~847 (1986)[DOI]
- H. C. Pocklington, "The direct solution of the quadratic and cubic binomial congruences with prime moduli", Proceedings of the Cambridge Philosophical Society, 19, pp.57~59 (1917)
- "Sage Reference Manual, Elements of Z/nZ"[URL]
- D. Shanks, "Five number-theoretic algorithms", Proceedings of the Second Manitoba Conference on Numerical Mathematics, pp.51~70 (1973)
- A. Tonelli, "Bemerkung uber die Auflosung Quadratischer Congruenzen", pp.344~346 (1891), Gottinger Nachrichten