PARALLEL MODULAR MULTIPLICATION WITH TABLE-LOOK-UP

Modular exponentiation with a large modulus (usually longer than 512 b its) is the main operation in most number-theoretic cryptosystems. A m odular exponentiation can be carried out by iteration of modular multi plications. Therefore, design of a fast modular multiplication algorit hm is the key to developing a high performance encryption/decryption c ircuit for such cryptosystems. Most existing algorithms are focused on the serial implementation of modular multiplication [1-7]. In this pa per, we present a new parallel algorithm which takes only (2.75 k + 1. 25) n-bit additions if the n-bit operands are divided into k blocks an d look-up table implemented with commercially available memory chips a re employed. The parallel algorithm can provide a speedup of (0.5 n/k) as compared with conventional iterative modular multiplication algori thm.