An Efficient Implementation of Montgomery Modular Multiplication Using a Minimally Redundant Residue Number System

This paper presents an implementation of modular multiplication based on Montgomery’s scheme within the Residue Number System (RNS). The key innovation of the proposed approach lies in utilizing minimally redundant residue arithmetic, where the rank of a number serves as the primary positional characteristic of the residue code. Additionally, integer numbers are represented in rank form during base extension operations. Due to the low computational complexity of rank calculation in minimally redundant RNS and the specific constraints imposed on the RNS moduli sets, the proposed modular multiplication method achieves up to a 1.5 times performance improvement over non-redundant RNS counterparts. This approach is particularly suited for applications in public key cryptosystems.