Fast algorithm for scalar multiplication in elliptic curves cryptography
Shen Yong · Jisuanji yingyong yanjiu · 2009
A field inversion is the most expensive operation on scalar multiplication,and the number of inversion determines the performance of scalar multiplication.Trading inversions for multiplications can decrease the number of inversion.Based on the idea,this paper proposed an efficient algorithm to compute 3P+Q directly over Fp in terms of affine coordinates,its computational complexity was 1I+3S+16M,saving one field inversion compared to Ciet's method.Moreover,also gave an improvement to compute 3kP directly,which was more efficient than k repeated 3P.Finally,applied the two algorithms to scalar multiplication combined with the representation of 3-NAFw.The result suggests that the scalar multiplication using 3P+Q and 3kP is faster than traditional methods,such as NAF,NAF4 and so on,and the ration I/M of break-even point can be reduced to 5.4.