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

摘要： 多个指数运算的乘积是公钥密码学中的一种重要运算。该文针对求逆元素的运算量较大的情形,提出了两种有效实现该运算的算法:在基固定和基不固定两种情况下,分别将多个指数表示成联合稀疏形和串代换形式,然后利用快速Shamir算法进行计算。分析表明,算法有效降低了快速Shamir算法的运算次数。

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