Modular multiplication hardware algorithms with a redundant representation and their application to RSA cryptosystem

摘要

Radix-2 and radix-4 modular multiplication hardware algorithms are proposed. Numbers are represented in a redundant representation and modular additions are performed without carry propagation. Serial-parallel modular multipliers based on them have a regular cellular array structure with a bit slice feature suitable for VLSI implementation. They are efficient especially in applications, such as an RSA cryptosystem, where modular multiplications are performed iteratively.