Abstract: 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 3nP have 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 kP by 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.

Key words: Elliptic curve cryptosystems,Scalar multipfication,Edwards curves,Triple formula,w-NNAF