On the Computation of Square Roots in Finite Fields

被引：0
作者：
Siguna Müller
机构：
[1] University of Calgary,Department of Mathematics and Statistics
来源：
Designs, Codes and Cryptography | 2004年 / 31卷
关键词：
finite fields; square roots; efficient computation; complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, two improvements for computing square roots in finite fields are presented. Firstly, we give a simple extension of a method by O. Atkin, which requires two exponentiations in FMq, when q≡9 mod 16. Our second method gives a major improvement to the Cipolla–Lehmer algorithm, which is both easier to implement and also much faster. While our method is independent of the power of 2 in q−1, its expected running time is equivalent to 1.33 as many multiplications as exponentiation via square and multiply. Several numerical examples are given that show the speed-up of the proposed methods, compared to the routines employed by Mathematica, Maple, respectively Magma.
引用
收藏
页码：301 / 312
页数：11
相关论文
共 13 条
  • [1] Atkin A. O. L.(1993)Elliptic curves and primality proving Math. Comp. 61 29-68
  • [2] Morain F.(1999)Note on taking square-roots modulo N IEEE Trans. Inf. Theory 45 807-809
  • [3] Bach E.(1970)Factoring polynomials over large finite fields Math. Comp. 24 713-735
  • [4] Huber K.(1903)Un metodo per la risolutione della congruenza di secondo grado Rendiconto dell'Accademia Scienze Fisiche e Matematiche, Napoli, Ser. 3 IX 154-163
  • [5] Berlekamp E. R.(1995)Factors of generalized fermat numbers Math. Comp. 64 397-405
  • [6] Cipolla M.(1998)A survey of fast exponentiation methods Journal of Algorithms 27 129-146
  • [7] Dubner H.(1999)An analysis of Shanks's algorithm for computing square roots in finite fields CRM Proceedings and Lecture Notes 19 231-242
  • [8] Keller W.(1980)Probabilistic algorithms in finite fields SIAM J. Comput. 9 273-280
  • [9] Gordon D.(1988)Fast evaluation of Dickson Polynomials Contrib. to General Algebra 6 223-225
  • [10] Lindhurst S.(1985)Elliptic curves over finite fields and the computation of square roots mod Math. Comp. 44 483-494
12