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 Reciprocals

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

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences      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)
Category:
Keyword:
Chinese remainder,  residue number system,  sign detection,  comparison,

Full Text: FreePDF(2.8MB)

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.