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

Read full text Summarise with VIRAT
Authors: Shinichi Kawamura, Yuichi Komano, Daisuke Fujimoto
Cited by: 0
References: 18

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

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.

Fields of Study & Subjects

Cryptography and Residue Arithmetic Cryptographic Implementations and Security Cryptography and Data Security

Publication details

Journal / source
IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences
Volume
E109.A
Issue
9
Pages
1483–1498
Publication date
25 March 2026
Language
EN