Fast modular multi-exponentiation using modified complex arithmetic
详细信息查看全文 | 推荐本文 |
摘要
Modular multi-exponentiation is a very important but time-consuming operation in many modern cryptosystems. In this paper, a fast modular multi-exponentiation is proposed utilizing the binary-like complex arithmetic method, complement representation method and canonical-signed-digit recoding technique. By performing complements and canonical-signed-digit recoding technique, the Hamming weight (number of 1’s in the binary representation or number of non-zero digits in the binary signed-digit representations) of the exponents can be reduced. Based on these techniques, an algorithm with efficient modular multi-exponentiation is proposed. For modular multi-exponentiation, in average case, the proposed algorithm can reduce the number of modular multiplications (MMs) from 1.503k to 1.306k, where k is the bit-length of the exponent. We can therefore efficiently speed up the overall performance of the modular multi-exponentiation for cryptographic applications.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址：北京市海淀区学院路29号 邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700