RNS bases and conversions

摘要

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.