## CryptoDB

### Paper: Complexity Analysis of a Fast Modular Multiexponentiation Algorithm

Authors: Haimin Jin Duncan S. Wong Yinlong Xu URL: http://eprint.iacr.org/2008/210 Search ePrint Search Google Recently, a fast modular multiexponentiation algorithm for computing A^X B^Y (mod N) was proposed. The authors claimed that on average their algorithm only requires to perform 1.306k modular multiplications (MMs), where k is the bit length of the exponents. This claimed performance is significantly better than all other comparable algorithms, where the best known result by other algorithms achieves 1.503k MMs only. In this paper, we give a formal complexity analysis and show the claimed performance is not true. The actual computational complexity of the algorithm should be 1.556k. This means that the best modular multiexponentiation algorithm based on canonical-sighed-digit technique is still not able to overcome the 1.5k barrier.
##### BibTeX
@misc{eprint-2008-17887,
title={Complexity Analysis of a Fast Modular Multiexponentiation Algorithm},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / Modular Multi-Exponentiation},
url={http://eprint.iacr.org/2008/210},
note={ duncan@cityu.edu.hk 14012 received 12 May 2008},
author={Haimin Jin and Duncan S. Wong and Yinlong Xu},
year=2008
}