RNS bases and conversions

Jean-Claude Bajard; Thomas Plantard

doi:10.1117/12.557891

26 October 2004 RNS bases and conversions

Jean-Claude Bajard, Thomas Plantard

Proceedings Volume 5559, Advanced Signal Processing Algorithms, Architectures, and Implementations XIV; (2004) https://doi.org/10.1117/12.557891
Event: Optical Science and Technology, the SPIE 49th Annual Meeting, 2004, Denver, Colorado, United States

Abstract

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.

Citation Download Citation

Jean-Claude Bajard and Thomas Plantard "RNS bases and conversions", Proc. SPIE 5559, Advanced Signal Processing Algorithms, Architectures, and Implementations XIV, (26 October 2004); https://doi.org/10.1117/12.557891

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available