On the Computation of Square Roots in Finite Fields

SIGUNA MUELLER

首页> 外文期刊>Designs, Codes and Crytography >On the Computation of Square Roots in Finite Fields

【24h】

On the Computation of Square Roots in Finite Fields

机译：关于有限域中平方根的计算

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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 F_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.

机译：本文提出了两种在有限域中计算平方根的改进方法。首先，我们给出O. Atkin方法的简单扩展，当q extension 9 mod 16时，它需要F_q有两个指数。我们的第二种方法对Cipolla-Lehmer算法进行了重大改进，既易于实现又易于实现。也快得多。虽然我们的方法不受q -1中2的幂的限制，但其预期运行时间等于1.33乘以平方和乘的幂。与Mathematica，Maple和Magma分别采用的例程相比，给出了几个数值示例，这些示例说明了所提出方法的速度。

著录项

来源
《Designs, Codes and Crytography》 |2004年第3期|p.301-312|共12页
作者
SIGUNA MUELLER;
展开▼
作者单位

Department of Mathematics and Statistics, University of Calgary 2500 University Drive N.W. Calgary, AB T2N 1N4 Canada;

展开▼
收录信息美国《科学引文索引》(SCI);美国《工程索引》(EI);
原文格式 PDF
正文语种 eng
中图分类高等数学;
关键词
finite fields; square roots; efficient computation; complexity;

机译：有限域;平方根;高效计算;复杂性;

相似文献

外文文献
中文文献
专利

1. Improved Computation of Square Roots in Specific Finite Fields [J] . Dong-Guk Han, Dooho Choi, Howon Kim IEEE Transactions on Computers . 2009,第2期

机译：特定有限域中平方根的改进计算
2. An Efficient Square Root Computation in Finite Fields GF(p~2~d ) [J] . Feng WANG, Yasuyuki NOGAMI, Yoshitaka MORIKAWA IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences . 2005,第10期

机译：有限域GF（p〜2〜d）中的有效平方根计算
3. Computing Square Roots in Finite Fields [J] . Ozdemir E. IEEE Transactions on Information Theory . 2013,第9期

机译：计算有限域中的平方根
4. Characterization of Easily Controllable Plants Based on the Finite Frequency Phase/Gain Property: A Magic Number {the square root of}(4 + 2{the square root of}2) in H{sub}∞ Loop Shaping Design [C] . Masaaki Kanno, Shinji Hara, Masahiko Onishi American Control Conference . 2007

机译：基于有限频率/增益特性的易于控制工厂的表征：一个魔号{H子}环形整形设计中的奇数{}的平方根（4 + 2 {2的平方根）
5. Character Sums and Hyperelliptic Curves Associated with Subsets of Finite Fields with Square Order. [D] . Simon, Lois Susan. 2011

机译：与平方阶有限域子集相关的字符和和超椭圆曲线。
6. On Measuring the Root-Mean-Square Value of a Finite Record Length Periodic Waveform [O] . E. Clayton Teague 1989

机译：测量有限记录长度周期波形的均方根值
7. Elliptic curves over finite fields and the computation of square roots mod $p$ [O] . Ren{é Schoof 1985

机译：椭圆曲线在有限的领域和方形rotoot mod $ p $的计算
8. Storage and computationally efficient permutations of factorized covariance and square-root information arrays [R] . Muellerschoen, R. J. 1988

机译：分解协方差和平方根信息数组的存储和计算上有效的排列

On the Computation of Square Roots in Finite Fields

摘要

著录项

相似文献

相关主题

期刊订阅