Abstract:Scalar multiplication is the dominant and time consuming algorithm in elliptic curve cryptography, including point addition and point doubling. Traditional improved methods reduced the calculation of point addition by transforming the representation of scalar to reduce the number of non-zero bits. To further improve the efficiency of the scalar multiplication, this paper proposes an improved algorithm combining pseudo-random number generator according to the generation of the scalar. With cyclical iterative addition of lagged Fibonacci generator, scalar multiplication can be transformed into simplex operation of point addition from repetitive point addition and point doubling. Experimental results show that the improved algorithm compared to the traditional window NAF algorithm can reduce more than 60% of the amount of computation.