Computational efficiency analysis of Wu et al.’s fast modular multi-exponentiation algorithm

Very recently, for speeding up the computation of modular multi-exponentiation, Wu et al. presented a fast algorithm combining the complement recoding method and the minimal weight binary signed-digit representation technique. They claimed that the proposed algorithm reduced the number of modular mu...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics and computation 2007-07, Vol.190 (2), p.1848-1854
Main Authors: Sun, Da-Zhi, Huai, Jin-Peng, Sun, Ji-Zhou, Zhang, Jia-Wan
Format: Article
Language:English
Subjects:
Complement recoding
Computational efficiency
Exact sciences and technology
Markov chain
Mathematical analysis
Mathematics
Minimal weight binary signed-digit (BSD) representation
Modular multi-exponentiation
Numerical analysis
Numerical analysis. Scientific computation
Numerical methods in probability and statistics
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Very recently, for speeding up the computation of modular multi-exponentiation, Wu et al. presented a fast algorithm combining the complement recoding method and the minimal weight binary signed-digit representation technique. They claimed that the proposed algorithm reduced the number of modular multiplications from 1.503 k to 1.306 k on average, where the value k is the maximum bit-length of two exponents. However, in this paper, we show that their claim is unwarranted. We analyze the computational efficiency of Wu et al.’s algorithm by modeling it as a Markov chain. Our main result is that Wu et al.’s algorithm requires 1.471 k modular multiplications on average.
ISSN:0096-3003
1873-5649
DOI:10.1016/j.amc.2007.02.066