Parallel modular multiplication with table look-up

Abstract

Modular exponentiation with a large modulus (usually longer than 512 bits) is the main operation in most number-theoretic cryptosystems. A modular exponentiation can be carried out by iteration of modular multiplications. Therefore, design of a fast modular multiplication algorithm is the key to developing a high performance encryption/decryption circuit for such cryptosystems. Most existing algorithms are focused on the serial implementation of modular multiplication [1–7]. In this paper, we present a new parallel algorithm which takes only (2.75k + 1.25) n-bit additions if the n-bit operands are divided into k blocks and look-up table implemented with commercially available memory chips are employed. The parallel algorithm can provide a speedup of (0.5 n/k) as compared with conventional iterative modular multiplication algorithm.

Keywords:

• Modular multiplication
• table look-up method
• modular exponentiation
• parallel multiplication algorithm
• public-key cryptosystem

C.R. Categories:

• B.2.1
• E3
• F 2.1

^*Corresponding author.

^*Corresponding author.

Notes

^*Corresponding author.

Additional information

Notes on contributors

Che Wun Chiou

a