International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Complexity Analysis of a Fast Modular Multiexponentiation Algorithm

Authors:
Haimin Jin
Duncan S. Wong
Yinlong Xu
Download:
URL: http://eprint.iacr.org/2008/210
Search ePrint
Search Google
Abstract: 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
}