椭圆曲线中一种计算7P和7kP的改进算法

计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (1): 29-32.

椭圆曲线中一种计算7P和7kP的改进算法

赖忠喜，张安洁，张占军

台州职业技术学院机电工程学院，浙江台州 318000

出版日期:2016-01-01 发布日期:2015-12-30

Improved algorithms for computing 7P and 7kP on elliptic curves

LAI Zhongxi, ZHANG Anjie, ZHANG Zhanjun

College of Mechanical and Electrical Engineering, Taizhou Vocational Technical, Taizhou, Zhejiang 318000, China

Online:2016-01-01 Published:2015-12-30

摘要/Abstract

摘要： 为了提高椭圆曲线底层域运算的效率，基于将乘法运算转换为平方运算的思想，提出在素数域[GFP]上用仿射坐标直接计算[7P]和[7kP]的改进算法，其运算量分别为[I+18M+12S]和[I+(17k+2)M+(14k+1)S]，与已有的最好算法相比，效率分别提升了8.3%和10.3%。另外，基于相同的思想给出了素数域[GFP]上用仿射坐标系直接计算[5kP]的改进算法，其运算量为[I+(9k+2)M+(14k+1)S]，与徐凯平和Mishra等人所提的算法相比，效率分别提升了17.2%和35.7%。

null

关键词: 椭圆曲线密码体制, 标量乘法, 乘法, 底层域运算, 仿射坐标

Abstract: To raise the efficiency of field operations on elliptic curve, based on the idea of trading multiplications for squares, two improved algorithms are proposed to compute [7P] and [7kP] directly over [GFP] in terms of affine coordinates, their computational complexity is [I+18M+12S] and [I+(17k+2)M+(14k+1)S] respectively, and the new algorithm’s efficiency is improved by 8.3% and 13.5% respectively compared with the best algorithms at present. In addition, based on the same idea, a modified method is given to compute [5kP] directly over [GFP] in terms of affine coordinates, its computational complexity is [I+(9k+2)M+(14k+1)S], and the efficiency of the new method is improved by 17.2% and 35.7% respectively compared with Xu Kaiping’s and MISHRA’s method.

Key words: Elliptic Curve Cryptosystem（ECC）, scalar multiplication, multiplications, field operations, affine coordinate

赖忠喜，张安洁，张占军. 椭圆曲线中一种计算7P和7kP的改进算法[J]. 计算机工程与应用, 2016, 52(1): 29-32.

LAI Zhongxi, ZHANG Anjie, ZHANG Zhanjun. Improved algorithms for computing 7P and 7kP on elliptic curves[J]. Computer Engineering and Applications, 2016, 52(1): 29-32.

[1]	程帅，吴华锋，梅骁峻. 交替非负约束框架的海洋传感网协同定位[J]. 计算机工程与应用, 2021, 57(23): 129-136.
[2]	曹林根，宓超. 集装箱箱号字符识别算法研究[J]. 计算机工程与应用, 2021, 57(15): 178-185.
[3]	陈晓倩，刘瑞祥. 基于最小二乘策略迭代的无人机航迹规划方法[J]. 计算机工程与应用, 2020, 56(1): 191-195.
[4]	庞丽莉1，许其清1，谢家烨1，2. 椭球约束下减小三维定位中的非视距误差[J]. 计算机工程与应用, 2019, 55(7): 115-119.
[5]	杨海蓉1，金辉2. 改进的迭代重加权最小二乘非凸压缩感知算法[J]. 计算机工程与应用, 2018, 54(24): 46-51.
[6]	肖红德. 最少钱币数量的计算与钱币面额的确定[J]. 计算机工程与应用, 2018, 54(16): 266-270.
[7]	崔雪红，刘云，王传旭，李辉. 高显著性的时空金字塔精简描述符算法研究[J]. 计算机工程与应用, 2018, 54(1): 210-216.
[8]	高遵海，高颖，程果. 图的赋权路径矩阵与所有点对最短路径问题[J]. 计算机工程与应用, 2017, 53(9): 47-50.
[9]	张爱华，杨莉苹，林冬梅. 基于灰度矩的脉搏图像亚像素特征点提取研究[J]. 计算机工程与应用, 2017, 53(8): 224-229.
[10]	李胜1，张培林1，李兵2，吴定海1，周云川3. 改进的量子遗传偏最小二乘特征选择方法应用[J]. 计算机工程与应用, 2017, 53(3): 242-246.
[11]	张晓楠1，高献伟1，2，董秀则2. 基于FPGA的进位存储大数乘法器的改进与实现[J]. 计算机工程与应用, 2017, 53(21): 58-61.
[12]	马旭. 超高精度计算程序设计实例[J]. 计算机工程与应用, 2017, 53(14): 51-55.
[13]	霍倩倩1，田翔2，姜琳3，蔡翠莹3. 基于无线通信TOA值对终端定位问题的研究[J]. 计算机工程与应用, 2017, 53(13): 252-258.
[14]	刘双根1，姚华童1，李发根2. Edwards曲线上抗SPA快速标量乘算法[J]. 计算机工程与应用, 2017, 53(1): 103-106.
[15]	顾乐民. 对GM灰色模型及理论的分析[J]. 计算机工程与应用, 2016, 52(6): 1-7.