ANALYSIS OF COMPLEMENTS IN MULTI-EXPONENTIATION ALGORITHMS USING SIGNED DIGIT REPRESENTATIONS

摘要

Wu, Lou, Lai and Chang proposed a multi-exponentiation algorithm using binary complements and the non-adjacent form. The purpose of this paper is to give a precise asymptotic analysis of the expected costs of this algorithm. It turns out that the complement operation does not have significant influence on the performance of the algorithm.