Joint Triple-Base Number System for Multi-Scalar Multiplication

摘要

At present, the joint sparse form and the joint binary-ternary method are the most efficient representation systems for calculatingmultiscalar multiplications [k]P +[l]Q, where k, l are scalars and P,Qare points on the same elliptic curve. We introduce the concept of a joint triple-base chain. Our algorithm, named the joint binary-ternary-quintuple method, is able to find a shorter joint triple-base chain for the sparseness of triplebase number systems. With respect to the joint sparse form, this algorithmsaves 32% of the additions, saving 13% even compared with the joint binary-ternary method. The joint binary-ternary-quintuplemethod is the fastest method among the existing algorithms, which speeds up the signature verification of the elliptic curve digital signature algorithm. It is very suitable for software implementation.