Complexity Analysis of a Fast Modular Multiexponentiation Algorithm

Haimin Jin; Duncan S.  Wong; Yinlong Xu

Paper 2008/210

Complexity Analysis of a Fast Modular Multiexponentiation Algorithm

Haimin Jin, Duncan S. Wong, and Yinlong Xu

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Modular Multi-Exponentiation
Contact author(s): duncan @ cityu edu hk
History: 2008-05-21: received
Short URL: https://ia.cr/2008/210
License: CC BY

BibTeX

@misc{cryptoeprint:2008/210,
      author = {Haimin Jin and Duncan S.  Wong and Yinlong Xu},
      title = {Complexity Analysis of a Fast Modular Multiexponentiation Algorithm},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/210},
      year = {2008},
      url = {https://eprint.iacr.org/2008/210}
}