A New Algorithm of Elliptic Curve Multi-Scalar Multiplication
Dai Yi · Chinese Journal of Computers · 2008
The main operations of elliptic curve cryptosystem are scalar multiplication and multi-scalar multiplication for a pair of integers.In this paper,a new encoding algorithm,which transforms multiple integers into a new kind of signed binary representation of them,is presented.The new encoding algorithm needs only to handle two adjacent columns,and thus is fast and easy to implement.Using this new kind of joint signed binary expressions,a new elliptic curve multi-scalar multiplication algorithm is proposed.The analysis about its time complexity is given,and the comparisons of traditional methods and the new method are also presented,based on which the authors draw the conclusion that the new multi-scalar multiplication algorithm requires about 7% to 15% less running time than the known ones.