Improvement of a Montgomery Multiplication Algorithm in Single-Base Residue Number System

Most Montgomery multiplication algorithms using residue number system (RNS) representations are constructed using two sets of RNS bases (double bases), which involve representation extensions between the bases. In 2024, a new algorithm was proposed for calculating Montgomery multiplication using a single RNS base set (single base). Assuming that the size of the RNS base set is as k, although the typical number of multiplications increases from order 2k2 to 3k2, the single-base algorithm reduces the processing cycles from 2k of the double-base to k beause the single-base algorithm has more parallelism. This study first refines the single-base algorithm by changing the expression of variables from standard RNS to the RNS normalized by the complementary range, which we name the ξ-expression in this study. We then discuss how the number of multiplications can be reduced in specific multiplications, that is, squaring and constant multiplication. The reduction rate depends on k and asymptotically approaches two-thirds when k increases. These two multiplications are used in a binary exponentiation algorithm that is widely used to implement RSA cryptosystems. Third, we present an algorithm for lazy reduction using a single RNS base, which can be used to implement elliptic-curve cryptography. The lazy-reduction formula for a single-base RNS is suitable for parallel processing and thus requires fewer processing cycles than the formula for a double-base RNS. We evaluate the proposed algorithms from an algorithmic perspective using a simple hardware model.