A High-performance and Low-cost Montgomery Modular Multiplication Based on Redundant Binary Representation

In this brief, Redundant Binary Representation (RBR) is applied in Montgomery modular multiplication (MMM) to eliminate the long carry chain and realize parallel computation. A novel MMM algorithm based on RBR is proposed. Based on the proposed algorithm, different sizes of high-performance and low-cost Montgomery multipliers are implemented in TSMC CMOS process technology. The experimental results demonstrate that our design has significant advantages in terms of performance, area and Area-Time-Product over previous researches. It’s worth mentioning that our 8192-bit Montgomery multiplier (TMSC 65nm) with 603MHz working frequency and 878.1K equivalent gates can complete the MMM in only 3403ns.