椭圆曲线底层域快速算法的研究

Study on fast method of field operation in elliptic curves

为了提高椭圆曲线底层域运算的效率,基于将求逆转换为乘法运算的思想,提出了在素数域F P上用仿射坐标直接计算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%。

To raise the efficiency of field operation on elliptic curve, based on the idea of trading inversions for multiplica-tions, two efficient algorithms are proposed to compute 4P and 5P directly over prime field FP in terms of affine coordi-nates. 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 5k P 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.