Efficient Algorithms for Sign Detection in RNS Using Approximate Reciprocals

Shinichi KAWAMURA  Yuichi KOMANO  Hideo SHIMIZU  Saki OSUKA  Daisuke FUJIMOTO  Yuichi HAYASHI  Kentaro IMAFUKU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E104-A   No.1   pp.121-134
Publication Date: 2021/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2020CIP0020
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Chinese remainder,  residue number system,  sign detection,  comparison,  

Full Text: FreePDF

The residue number system (RNS) is a method for representing an integer x as an n-tuple of its residues with respect to a given set of moduli. In RNS, addition, subtraction, and multiplication can be carried out by independent operations with respect to each modulus. Therefore, an n-fold speedup can be achieved by parallel processing. The main disadvantage of RNS is that we cannot efficiently compare the magnitude of two integers or determine the sign of an integer. Two general methods of comparison are to transform a number in RNS to a mixed-radix system or to a radix representation using the Chinese remainder theorem (CRT). We used the CRT to derive an equation approximating a value of x relative to M, the product of moduli. Then, we propose two algorithms that efficiently evaluate the equation and output a sign bit. The expected number of steps of these algorithms is of order n. The algorithms use a lookup table that is (n+3) times as large as M, which is reasonably small for most applications including cryptography.