On the Computation of Square Roots in Finite Fields |
| |
Authors: | Siguna Müller |
| |
Institution: | (1) Department of Mathematics and Statistics, University of Calgary, 2500 University Drive N.W, Calgary, AB, T2N 1N4, Canada |
| |
Abstract: | 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 FM
q
, 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. |
| |
Keywords: | finite fields square roots efficient computation complexity |
本文献已被 SpringerLink 等数据库收录! |
|