For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Efficient Algorithms for Sign Detection in RNS Using Approximate ReciprocalsShinichi KAWAMURA  Yuichi KOMANO  Hideo SHIMIZU  Saki OSUKA  Daisuke FUJIMOTO  Yuichi HAYASHI  Kentaro IMAFUKU  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E104-A   No.1   pp.121-134Publication Date: 2021/01/01Online ISSN: 1745-1337 DOI: 10.1587/transfun.2020CIP0020Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)Category: Keyword: Chinese remainder,  residue number system,  sign detection,  comparison,  Full Text: FreePDF Summary:  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.