Efficient Algorithms for Sign Detection in RNS Using Approximate Reciprocals

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

doi:10.1587/transfun.2020CIP0020

Open Access
Efficient Algorithms for Sign Detection in RNS Using Approximate Reciprocals

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

Full Text Views

99

Cite this

Free PDF (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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.1 pp.121-134

Publication Date: 2021/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2020CIP0020

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Authors

Shinichi KAWAMURA
  ECSEC Technical Research Association,Toshiba Corporation,National Institute of Advanced Industrial Science and Technology
Yuichi KOMANO
  Toshiba Corporation
Hideo SHIMIZU
  Toshiba Corporation
Saki OSUKA
  Nara Institute of Science and Technology
Daisuke FUJIMOTO
  Nara Institute of Science and Technology
Yuichi HAYASHI
  National Institute of Advanced Industrial Science and Technology,Nara Institute of Science and Technology
Kentaro IMAFUKU
  National Institute of Advanced Industrial Science and Technology

Keyword

Chinese remainder, residue number system, sign detection, comparison

Cite this

Copy

Shinichi KAWAMURA, Yuichi KOMANO, Hideo SHIMIZU, Saki OSUKA, Daisuke FUJIMOTO, Yuichi HAYASHI, Kentaro IMAFUKU, "Efficient Algorithms for Sign Detection in RNS Using Approximate Reciprocals" in IEICE TRANSACTIONS on Fundamentals, vol. E104-A, no. 1, pp. 121-134, January 2021, doi: 10.1587/transfun.2020CIP0020.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020CIP0020/_p

Copy

@ARTICLE{e104-a_1_121,
author={Shinichi KAWAMURA, Yuichi KOMANO, Hideo SHIMIZU, Saki OSUKA, Daisuke FUJIMOTO, Yuichi HAYASHI, Kentaro IMAFUKU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Algorithms for Sign Detection in RNS Using Approximate Reciprocals},
year={2021},
volume={E104-A},
number={1},
pages={121-134},
abstract={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.},
keywords={},
doi={10.1587/transfun.2020CIP0020},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Efficient Algorithms for Sign Detection in RNS Using Approximate Reciprocals
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 121
EP - 134
AU - Shinichi KAWAMURA
AU - Yuichi KOMANO
AU - Hideo SHIMIZU
AU - Saki OSUKA
AU - Daisuke FUJIMOTO
AU - Yuichi HAYASHI
AU - Kentaro IMAFUKU
PY - 2021
DO - 10.1587/transfun.2020CIP0020
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2021
AB - 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.
ER -