Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (1): 29-32.

Previous Articles     Next Articles

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

LAI Zhongxi, ZHANG Anjie, ZHANG Zhanjun   

  1. College of Mechanical and Electrical Engineering, Taizhou Vocational Technical, Taizhou, Zhejiang 318000, China
  • Online:2016-01-01 Published:2015-12-30

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

赖忠喜,张安洁,张占军   

  1. 台州职业技术学院 机电工程学院,浙江 台州 318000

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.

null

Key words: Elliptic Curve Cryptosystem(ECC), scalar multiplication, multiplications, field operations, affine coordinate

摘要: 为了提高椭圆曲线底层域运算的效率,基于将乘法运算转换为平方运算的思想,提出在素数域[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%。

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