【摘要】 求逆是标量乘法中最耗时的运算,求逆运算次数的多少直接决定标量乘法的性能。转换求逆为乘法运算能够降低求逆次数。根据这种思想,提出了素域Fp上用仿射坐标直接计算3P+Q的算法,其运算量为1I+3S+16M,比Ciet等人提出的方法节省了一次求逆运算。同时还给出直接计算3kP的算法,该算法比重复计算k次3P更有效。最后结合3-NAFw的编码方法,把两个新算法应用到标量乘法中。结果表明,运用3P+Q、3kP的标量乘法比传统的NAF、NAF4等方法更有效,相交处I/M的值可降为5.4。更多还原

【Abstract】 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.更多还原