A New Mutual Opposite Form Based Left-to-Right Multi-Scalar Multiplication Algorithm
Cheng Yi-fei · Computer Technology and Development · 2007
Many elliptic curve based cryptographic protocols require computation of multiple scalar multiplications such as kP+lQ.Common methods to compute it are the Shamir method and the interleaving method whereas their speed mainly depends on the(joint) Hamming weight of the scalars.The joint sparse form of two L-bit integers has an average joint Hamming weight of L/2,which is an optimal-weight signed-binary representation,but it can be implemented only from right to left.In this paper,a new recoding method based on the mutual opposite form is proposed.This form has the same average Joint Hamming weight as the JSF.And a new MOF representation based multiple scalar multiplication algorithm is given.This method examines the integers from left to right.This results in the merging of recoding and evaluation stages.So the proposed algorithm can improve the performance and reduce the memory consumption of scalar multiplication operation.