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

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

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