ANALYSIS OF MULTI-EXPONENTIATION ALGORITHM USING BINARY SIGNED-DIGIT REPRESENTATIONS

摘要

We concentrate our attention on the computational efficiency analysis of the multiexponentiation algorithm using Yang et al.'s BSD representation, which is the generalization of Dimitrov et al.'s BSD representation. Our theoretical results are that the average number of multiplications is at least 1.527n by Yang et al.'s BSD representation and 1.537n by Dimitrov et al.'s BSD representation, where n is the bit-length of the exponents.