Fast Scalar Multiplication on Edwards Curves Based on w-NNAF
Wenlong Qu · 2010
Based on analysing and using the triple formula of Edwards curve to calculate 3nP(n=1,2,…),according to circumstances that the coordinate of every 3nPhave the unitive representation,we put forward a new algorithm Tripling-Algorithm which can quickly compute 3nP(n=2,3…)by reducing inverse operation.And combining this algorithm with the w-NNAF representation with scalar k,we gave a kind of highly efficient algorithm ImprovedSM-3-NNAF to calculate scalar multiplication kP(for short ImprovedSM-3-NNAF).The analysis of the complexity and security of the Improved SM-3-NNAF shows that not only calculating kPby using this algorithm is security,but also it can save the amount of calculation by at least 20.78%,and has greatly improved the computational efficiency of the scalar multiplication in Edwards curve.