13 November 2000 Some improvements on RNS Montgomery modular multiplication
Author Affiliations +
In Residue Number Systems (RNS), an integer X is represented by its residues {x0,...,xn-1} modulo a base of relatively prime numbers {m0,...,mn-1}. Thus a large number can be represented as a set of small integers. Addition and multiplication can be easily parallelized, there is no carry propagation. The time is reduced to the evaluation of these operations with small numbers. This representation is useful in cryptography and digital signal processing. Furthermore, in these two domains, modular multiplication (A X B mod N) is frequently used. So, in 1998, we have presented in IEEE journal of transactions on computers, a new modular multiplication algorithm in RNS. This algorithm is based on the Montgomery algorithm, using the associated Mixed Radix representation, for the weighted digits. It was the first algorithm of this type. In this paper, we present two remarks. First, if we develop the different expressions due to the algorithm, we obtain some mathematical simplifications that allow us to suppress some Mixed Radix occurrence in the basic iteration simply with a new initialization of our variables. Thus, in this new version, the complexity of each basic iteration, becomes equivalent to two products of small integers instead of three. The second remark is that, most of the time, modular multiplications are done with the same modulo N. We can precompute some values and reduce the complexity of each basic iteration to one multiplication of two small integers. Thus, the basic iteration is three times faster, and the global computation, due to the initialization, is 8/5 time faster than the original version. Sometime after the last basic iteration a Mixed Radix conversion can be needed. Classical parallel methods are linear. We propose an algorithmic parallel algorithm for this translation from RNS to Mixed Radix. For this, we use a result that comes from an RNS division algorithm, we published in Journal of VLSI signal processing systems 1998. We obtain in a logarithmic time an approximation of the Mixed radix representation. The correct representation is then established in a logarithmic time too.
© (2000) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Jean-Claude Bajard, Jean-Claude Bajard, Laurent-Stephane Didier, Laurent-Stephane Didier, Peter Kornerup, Peter Kornerup, Fabien Rico, Fabien Rico, } "Some improvements on RNS Montgomery modular multiplication", Proc. SPIE 4116, Advanced Signal Processing Algorithms, Architectures, and Implementations X, (13 November 2000); doi: 10.1117/12.406499; https://doi.org/10.1117/12.406499


Prototype coprocessor for image algebra operations
Proceedings of SPIE (June 22 1993)
RNS bases and conversions
Proceedings of SPIE (October 25 2004)
Tools for mapping applications to CCMs
Proceedings of SPIE (October 07 1998)
A comparative study of modular adders
Proceedings of SPIE (October 25 2004)
Redundant finite rings for fault-tolerant signal processors
Proceedings of SPIE (October 27 1994)

Back to Top