Share Email Print

Proceedings Paper

RNS bases and conversions
Author(s): Jean-Claude Bajard; Thomas Plantard
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 26 October 2004
PDF: 10 pages
Proc. SPIE 5559, Advanced Signal Processing Algorithms, Architectures, and Implementations XIV, (26 October 2004); doi: 10.1117/12.557891
Show Author Affiliations
Jean-Claude Bajard, LIRMM-CNRS (France)
Univ. de Montpellier 2 (France)
Thomas Plantard, LIRMM-CNRS (France)
Univ. de Montpellier 2 (France)

Published in SPIE Proceedings Vol. 5559:
Advanced Signal Processing Algorithms, Architectures, and Implementations XIV
Franklin T. Luk, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?