## Abstract

A lot of research and system developments on the public key cryptosystem have been done in the last decade. In most of famous public key cryptosystems, the main task of the encryption and decryption engine is to compute the modular multi-exponentiation ∏_{i=1}^{n}M_{i}^{Ei} (mod N), where all the values of E_{i}'s are positive integers and n is equal to or greater than one. Several methods of fast exponentiation have been proposed in the past years to make the implementation of public key cryptosystems easierhowever, there are only a few parallel mechanisms for evaluating the modular multi-exponentiation. In this paper, we propose an efficient method for parallel computation of modular multi-exponentiation. On average, the time complexity of our proposed method for computing ∏_{i=1}^{n}M_{i}^{Ei}(mod N) is O(k_{max}/2^{n}) multiplication time units, where k_{max} is the maximal bit-length among all bit-lengths of E_{i}'s.

Original language | English |
---|---|

Pages (from-to) | 111-117 |

Number of pages | 7 |

Journal | Computer Systems Science and Engineering |

Volume | 15 |

Issue number | 2 |

State | Published - 2000 |

Externally published | Yes |

## Keywords

- Multi-exponentiation
- Parallel algorithms
- Parallel processing
- Prefix computation
- Public key cryptosystems
- The binary method
- Wormhole routing