Abstract: To raise the efficiency of field operation on elliptic curve, based on the idea of trading inversions for multiplications, two efficient algorithms are proposed to compute 4P and 5P directly over prime field [FP] in terms of affine coordinates. Their computational complexity are I+7M+8S and I+12M+10S respectively, which are improved to 4.6% and 2.6% respectively than those of Duc-Phong’s and Xu Kaiping’s method. Moreover, a fast method is given to compute [5kP] directly in terms of affine coordinates. Its computational complexity is [I+(15k+1)M+(10k-1)S,] and the efficiency of the new method is improved to 5.7% and 26.8% respectively than those of Xu Kaiping’s and Mishra’s method.

Key words: elliptic curve cryptosystem, scalar multiplication, field operation, affine coordinate, field inversion

摘要： 为了提高椭圆曲线底层域运算的效率，基于将求逆转换为乘法运算的思想，提出了在素数域[FP]上用仿射坐标直接计算4P和5P的快速算法，其运算量分别为I+7M+8S和I+12M+10S，与Duc-Phong和徐凯平等人所提的算法相比，效率分别提升了4.6%和2.6%。同时在仿射坐标下给出了一种直接计算[5kP]的快速算法，其运算量为[I+(15k+1)M+][(10k-1)S]，与徐凯平和Mishra等人所提的算法相比，效率分别提升了5.7%和26.8%。

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