关键词: 公钥密码, 数字签名, 指数运算乘积, 联合稀疏形

Abstract: Multi-exponentiation is one of the important operation for public key cryptography. This paper presents two effective algorithms for multi-exponentiation when the inverse element is not easy to compute. First, transferring the exponents to joint sparse form and string-replacement form for fixed-base and unfixed-base multi-exponentiation separately; and then using the fast Shamir algorithm to obtain the result. The new algorithms reduce the operation number of fast Shamir algorithm effectively.

Key words: public key cryptography, digital signature, multi-exponentiation, joint sparse form