Algorithm of asynchronous binary signed-digit recoding on fast multiexponentiation

doi:10.1016/j.amc.2004.06.107

Algorithm of asynchronous binary signed-digit recoding on fast multiexponentiation

2005-08-01

7

PRE

AI

DOI：10.1016/j.amc.2004.06.107

Original

Original request for help

Save

Abstract

En 中文

Multiexponentiation, for the 2-dimension one especially, is a very important but time-consuming operation in many ElGamal-like public key cryptosystems. An efficient multiexponentiation method is firstly proposed by Shamir in ElGamal's paper. Shamir's method requires 1.75n modular multiplications in average, where n is the bit-length of the exponents. Using minimal weight binary signed-digit (BSD) representations in Shamir's method can reduce the number of multiplications to 1.556n. Due to there are many minimal weight BSD representations for an integer, Dimitrov et al. proposed a new 2-dimension multiexponentiation algorithm to recode the canonical binary signed-digit representations. The average number of the number 1.556n is reduced to 1.534n. After the publish of the Dimitrov Jullien-Miller algorithm, there are many research on receding BSD representation of a pair of integers. The most interesting one is the joint sparse form. The number of multiplication can be reduced to 1.500n in joint sparse form when the exponent length is near infinite. In this paper, we propose a new asynchronous recoding algorithm to reduce the factor to 1.509n. For comparison to all the previous algorithm, the property of asynchronous receding is especially suitable for multi-dimension multiexponentiation. (c) 2004 Elsevier Inc. All rights reserved.

Keywords:

binary signed-digit (BSD) representation

multiexponentiation

public key cryptography

Algorithm of asynchronous binary signed-digit recoding on fast multiexponentiation

Abstract

Journal

Organization