Home > Cryptocurrency > Residue Number Systems

Residue Number Systems


 

Abstract

Residue Number systems have been extensively studied in past four decades in view of their advantages in some applications in Digital Signal Processing and Cryptography. In this tutorial paper, we introduce the basic concepts highlighting the advantages and
disadvantages over other number systems.

Introduction

Digital computation and Digital signal processing need arithmetic processors of moderate word lengths 16 to 32 bits.Fixed point and floating point arithmetic units which can perform addition, subtraction, multiplication are extensively employed. On the other hand, several cryptographic algorithms used for authentication such as RSA (Rivest,Shamir and Adleman) cryptosystems [1] need to perform operations on large word length operands of lengths ranging from 1024 bits to 4096 bits. Other authentication systems use Elliptic Curve Cryptography [2] where word lengths range from 160 bits to 256 bits. These can be realized in embedded systems using resident processors such ARM or using DSPs using word based implementations. In some applications such as Homomorphic encryption [3] used for computing on encrypted data in cloud computing, processors need to handle words of the size 768, 000 bits. Residue Number Systems facilitate handling such big number operations using smaller word length processors.

In the last decade, considerable research has been carried out in this area in order to design faster, low area and power efficient processors. Just as in the case of other Arithmetic and logic units, a RNS based Arithmetic unit needs to perform basic operations such as addition, subtraction, multiplication, scaling or division, comparison and sign detection.

We will consider these in the next few sections in some detail. We will present several example to facilitate easy understanding and avoid too much of theory.

Let us consider a conventional 32 bit processor for illustration. It needs to perform several 32 bit operations.Consider simple addition of two binary numbers. The time needed using carry
propagate adders or Ripple carry adders is 31 full-adder delays. Most text books [4], [5] give improved designs using carry-look-ahead techniques involving two or more levels so as to reduce the delay for computing the carrybit. Today the benchmark is roughly log2n full adder delay for a n-bit two operand addition. Thus for a given technology (i.e. specified gate delay), this is the minimum time needed. This can be reduced only if we use smaller width operands. Thus, one solution is to represent the 32 bit word using smaller numbers and then being able to perform operations faster. Earlier logarithmic systems have been tried which can convert the time consuming multiplication or division operations to addition and subtraction. But we need log tables to convert from normal form to logarithms and after multiplication or division conversion back to normal form. Unfortunately, addition and subtractions cannot be done easily in logarithmic number system.

RNS was introduced by Garner [6]. Szabo and Tanaka [7] and Watson and Hastings [8] have documented the research results in 1967 and have addressed the various issues and design of digital computers using RNS using electronic components available at that time including magnetic memories etc was described.

The concept of RNS is attributed to Chinese who have discovered the so called Chinese Remainder Theorem.

The problem given by Sun Tzu in 3rd Century is as follows:

  • We have things of which we do not know the number
  • If we count them by threes, wehave two left over
  • If we count them by fives, we have three left over
  • If we count them by sevens, we have two left over

1 2 3 4 5

Leave a Comment:

Your email address will not be published. Required fields are marked *