椭圆曲线中直接计算7P的方法及其应用
开篇：润墨网以专业的文秘视角，为您筛选了一篇椭圆曲线中直接计算7P的方法及其应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
文章编号:10019081(2013)07187005
doi:10.11772/j.issn.10019081.2013.07.1870
摘 要：
为了提高椭圆曲线标量乘法的效率，根据将求逆转换为乘法运算的思想，提出了在二进制域F2n上用仿射坐标直接计算7p的两种算法。两种算法分别通过引入公因子和除法多项式来计算7P，其运算量分别为2I+7S+14M和I+6S+20M，比Purohit等提出的算法(PUROHIT G N, RAWAT S A, KUMAR M. Elliptic curve point multiplication using MBNR and Point halving. International Journal of Advanced Networking and Applications, 2012, 3(5)： 1329-1337)分别节省了一次和两次求逆运算。同时还给出直接计算7kP的快速算法，该算法比重复计算k次7P更有效。最后结合半点运算和扩展多基表示形式将这些新算法应用到标量乘法中。实验结果表明，在美国国家标准技术研究所(NIST)推荐的椭圆曲线上，当预存储点的个数为2和 5时，新算法比Purohit算法效率提高了30%和37%,比洪银芳等所提的算法(洪银芳，桂丰，丁勇.基于半点和多基表示的标量乘法扩展算法.计算机工程,2011,37(4)：163-165)效率提高了9%和13%。新算法以增加少量的预计算存储为代价，能有效降低标量乘法的运算量。
关键词：椭圆曲线密码体制；标量乘法；半点运算；扩展多基表示；仿射坐标
中图分类号：TP309.7
文献标志码:A
英文标题
Algorithm for directly computing 7P elliptic curves and its application
英文作者名
LAI Zhongxi*, ZHANG Zhanjun, TAO Dongya
英文地址(
College of Mechanical and Electrical Engineering, Taizhou Vocational and Technical College, Taizhou Zhejiang 318000, China英文摘要)
Abstract：
To raise the efficiency of scalar multiplication on elliptic curve, based on the idea of trading inversions for multiplications, two efficient algorithms were proposed to compute 7P directly over binary field F2n in terms of affine coordinates. The common divisor and division polynomial were respectively introduced to compute 7P in two algorithms, their computational complexity were 2I+7S+14M and I+6S+20M, saving one inversion and two inversions respectively, compared with the Purohit′s method (PUROHIT G N, RAWAT S A, KUMAR M. Elliptic curve point multiplication using MBNR and Point halving. International Journal of Advanced Networking and Applications, 2012, 3(5)： 1329-1337). Moreover, a new method was given to compute 7kP directly, which was more efficient than computing 7P for k times. Finally, these new algorithms were applied to scalar multiplication combined with point halving and extended MBNS(Multi-Base Number Representation). The experimental results show that the efficiency of the new method is improved about 30%-37% over the Purohits method and about 9%-13% over the Hongs method (HONG Y F, GUI F, DING Y. Extended algorithm for scalar multiplication based on point halving and puter Engineering, 2011, 37(4)： 163-165) on the elliptic curves recommended by NIST(National Institute of Standards and Technology), when the number of prestorages points is 2 and 5. The new method can reduce the computational complexity of scalar multiplication efficiently with a few more precomputation storage.
To raise the efficiency of scalar multiplication on elliptic curve, based on the idea of trading inversions for multiplications, two efficient algorithms were proposed to compute 7P directly over binary field F2n in terms of affine coordinates. The common divisor and division polynomials were respectively introduced to compute 7P in two algorithm, their computational complexity were 2I+7S+14M and I+6S+20M, saving one inversion and two inversions respectively, compared with the Purohit′s method (PUROHIT G N, RAWAT S A, KUMAR M. Elliptic curve point multiplication using MBNR and Point halving. International Journal of Advanced Networking and Applications, 2012, 3(5)： 1329-1337). Moreover, a new method was given to compute 7kP directly, which was more efficient than k repeated 7P. Finally, these new algorithms were applied to scalar multiplication combined with point halving and extended MBNS. The experimental results show that the efficiency of the new method is improved about 30%~37% over the Purohit′s method and about 9%~13% over the HONG Y f′s method (HONG Y F, GUI F, DING Y. Extended algorithm for scalar multiplication based on point halving and puter Engineering, 2011, 37(4)： 163-165) on the elliptic curves recommended by NIST, When the number of prestorages points are 2 and 5. The new method can reduce the computational complexity of scalar multiplication efficiently at the cost of a few precomputations and storages.