素数域GF(P)上椭圆曲线快速标量乘算法的研究

Study on fast method of scalar multiplication on elliptic curves over Prime field GF(P)

基于求逆转换为乘法的思想,利用仿射坐标提出了直接计算椭圆曲线上7P的算法,该算法运算量为I+23M+10S,比现有的算法节省了一次求逆运算,同时也给出了直接计算7kP的快速算法,该算法比重复计算k次7P更有效。结合多基数系统将这些新算法应用到标量乘法中,实验结果表明,在NIST推荐的椭圆曲线上,新算法的效率优于徐凯平等人所提的算法及传统的ternary-binary、3-NAF、Dimitro算法,相交处I/M可降至2.4。

Based on the idea of trading inversions for multiplications, an efficient algorithm is proposed to compute 7P directly over prime field FPin terms of affine coordinates, its computational complexity is I＋23M＋10S, saving one inversion compared with traditional method. Moreover, a new method is given to compute 7kP directly, which is more efficient than k repeated 7P. Finally, apply these new algorithms to scalar multiplication combined with MBNS. The experimental results show that on the elliptic curves recommended by NIST, the efficiency of new algorithm is superior to algorithm given by Xu kai-ping and other traditional algorithms, such as ternary-binary, 3-NAF, Dimitro algorithms, and the ration I/M of break-even point can be reduced to 2.4.