Residue Number Systems (RNS) allow the distribution of large dynamic range computations over small modular rings, which allows the speed up of computations. This feature is well known, and already used in both DSP and cryptography. Most of implementations use RNS bases of three elements to reduce the complexity of conversions, but if can increase the number of RNS modular computational channels, then we are able to compute over smaller rings and thus further increase the speed of computation. In this paper, we deal with conversion from RNS to RNS or RNS to standard representations of numbers. We find, in the literature, two classes of conversion algorithms: those directly based on the chinese remainder theorem and those which use an intermediate Mixed Radix representation. We analyze these two different methods, show where the choice of the base is important and discuss the base selection criteria. We deduce that MRS conversions offer more possibilities than the CRT conversions. We provide features of RNS bases which provide low complexity of both RNS computation and conversion. We introduce some examples of bases well suited for cryptography applications.
© (2004) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Jean-Claude Bajard, Jean-Claude Bajard, Thomas Plantard, Thomas Plantard, } "RNS bases and conversions", Proc. SPIE 5559, Advanced Signal Processing Algorithms, Architectures, and Implementations XIV, (26 October 2004); doi: 10.1117/12.557891; https://doi.org/10.1117/12.557891


Back to Top