基于Montgomery的分段并行标量乘快速算法

Subsection simultaneous fast scalar multiplication algorithm based on Montgomery algorithm

在椭圆曲线二进制域上,Montgomery算法利用在计算kP过程中只需计算x坐标,在最后才恢复y坐标的特性,使该算法的计算量更少。在此基础上提出基于Montgomery的分段并行标量乘算法来更进一步提高算法的效率,经分析,将整数标量分两段并行计算,算法效率可提高约25%,将其分三段时其效率可提高约37%。通过编程实现验证了新算法的效率确实有明显提高,新算法对椭圆曲线标量乘快速实现有实际意义。

In the elliptic curve binary field,it needs less computation amount for that the Montgomery algorithm only computes the x coordinate in the whole course and gets the y coordinate in the last step.A new computational algorithm based on the Montgomery subsection method is proposed to enhance the efficiency further for computer kP, the computation amount decreases 25% for the new algorithm of two subsection and 37% for the new algorithm of three subsection compared with the original algorithm.The efficiency of the new algorithm is proved to be improved by the program implementation.The new algorithm possesses good performance on elliptic curve scalar multiplication.