Fast modular multi-exponentiation using modified complex arithmetic

Chia Long Wu*, Der Chyuan Lou, Jui Chang Lai, Te Jen Chang

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

11 Scopus citations

Abstract

Modular multi-exponentiation ∏i = 1n MiEi (mod N) is a very important but time-consuming operation in many modern cryptosystems. In this paper, a fast modular multi-exponentiation is proposed utilizing the binary-like complex arithmetic method, complement representation method and canonical-signed-digit recoding technique. By performing complements and canonical-signed-digit recoding technique, the Hamming weight (number of 1's in the binary representation or number of non-zero digits in the binary signed-digit representations) of the exponents can be reduced. Based on these techniques, an algorithm with efficient modular multi-exponentiation is proposed. For modular multi-exponentiation, in average case, the proposed algorithm can reduce the number of modular multiplications (MMs) from 1.503k to 1.306k, where k is the bit-length of the exponent. We can therefore efficiently speed up the overall performance of the modular multi-exponentiation for cryptographic applications.

Original languageEnglish
Pages (from-to)1065-1074
Number of pages10
JournalApplied Mathematics and Computation
Volume186
Issue number2
DOIs
StatePublished - 15 03 2007
Externally publishedYes

Keywords

  • Complex arithmetic
  • Hamming weight
  • Multi-exponentiation
  • Public key cryptography
  • Signed-digit recoding

Fingerprint

Dive into the research topics of 'Fast modular multi-exponentiation using modified complex arithmetic'. Together they form a unique fingerprint.

Cite this