A Generic Modulo-$(2^n\pm \hat{I}´)$ RNS Multiplier Based on Twit Representation

Abstract

Modular multiplication is a fundamental arithmetic primitive in Residue Number Systems (RNS) and is often the dominant source of delay, area, and energy consumption in RNS datapaths used in cryptography, signal processing, and machine-learning accelerators. Recent work introduced a twit-based residue representation for moduli of the form $2^n\pm \hat{I}´$, with $0\le \hat{I}´\le 2^{n-1}-1$, and showed that it enables efficient generic modular addition and subtraction across the full admissible $\hat{I}´$ range. However, an efficient modular multiplier compatible with the same representation has remained unavailable. This paper presents a generic twit-based modulo-$(2^n\pm \hat{I}´)$ multiplier for RNS channels. The proposed architecture computes the product through operand splitting, modular partial-product generation, carry-save accumulation, overflow folding, and a twit-compatible final modular addition. By deferring carry propagation to the final stage, the resulting organization avoids the long critical paths characteristic of conventional multiply-then-reduce designs. To demonstrate the effectiveness of the proposed approach, we study a modulus set with 5-bit residue channels and show that, owing to the broad admissible range of $\hat{I}´$, it can provide a sufficiently wide dynamic range. Moreover, additional 8-bit and 11-bit configurations are used to evaluate the proposed approach at larger channel widths. We implement and synthesize the proposed multiplier in a FreePDK 45\,nm flow, and the results show average reductions of 20.5\% in delay, 13.2\% in area, and 28.0\% in power relative to baseline designs. A system-level study further indicates that these circuit-level improvements translate into lower end-to-end latency over a broad range of modular multiplication and addition workloads.

13 pages, 8 figures