Paper 2008/210 Original: eprint.iacr.org/2008/210 ↗
Complexity Analysis of a Fast Modular Multiexponentiation Algorithm
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
- Preprint.
- History
- 2008-05-21: last updated
- 2008-05-21: published
- Short URL
- https://ia.cr/2008/210
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}