Call for Paper - January 2023 Edition
IJCA solicits original research papers for the January 2023 Edition. Last date of manuscript submission is December 20, 2022. Read More

Optimising the New Chinese Remainder Theorem 1 for the Moduli Set

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2016
Authors:
John Bosco Aristotle K. Ansuura, Ismail Rashid Fadulilahi
10.5120/ijca2016906811

John Bosco Aristotle K Ansuura and Ismail Rashid Fadulilahi. Optimising the New Chinese Remainder Theorem 1 for the Moduli Set. International Journal of Computer Applications 148(4):1-7, August 2016. BibTeX

@article{10.5120/ijca2016906811,
	author = {John Bosco Aristotle K. Ansuura and Ismail Rashid Fadulilahi},
	title = {Optimising the New Chinese Remainder Theorem 1 for the Moduli Set},
	journal = {International Journal of Computer Applications},
	issue_date = {August 2016},
	volume = {148},
	number = {4},
	month = {Aug},
	year = {2016},
	issn = {0975-8887},
	pages = {1-7},
	numpages = {7},
	url = {http://www.ijcaonline.org/archives/volume148/number4/25742-2016906811},
	doi = {10.5120/ijca2016906811},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

This paper seeks to improve the performance of the New Chinese Remainder Theorem (CRT) using the new moduli set {2^(2n+2)+3,2^(2n+1)+1,2^2n+1,2}. This optimization is very important in order to minimize the cost of hardware implementation and to improve the reverse conversion speed. The major factor responsible for this high hardware cost and high reverse conversion time is the presence of multipliers in the hardware implementation of the reverse converters. This paper proposes the moduli set {2^(2n+2)+3,2^(2n+1)+1,2^2n+1,2}, which is applicable for applications requiring larger dynamic range. The moduli set must be relatively prime integers. The computation of multiplicative inverses can be eliminated. We employ the proposed moduli set to optimize the New CRT-I. This scheme can result in less memory and adder based reverse converters, which is shown to be better than known existing similar state of the art scheme.

References

  1. Cao B., Chang C., Sirkanthan T (1998) A residue-to-binary converter for a new five-moduli set, IEEE Transactions on Circuits and Systems, 35 (11).
  2. Conway R. and Nelson J. (2004) Improved RNS FIR Filter Architectures, IEEE Transactions On Circuits and Systems II, Vol. 51, No. 1, pp. 26-28.
  3. Daabo M.I and Gbolagade K.A.Overflow Detection Scheme in RNS Multiplication Before Forward Conversion Journal of computing, Volume 4, Issue 12, pp. 13-16, December 2012 ISSN (Online) 2151-9617
  4. Daabo M.I and Gbolagade K.A. RNS Overflow Detection Scheme for the Moduli Set {M-1, M}.Journal of computing, Vol. 4, Issue 8 pp.39-44, August 2012 ISSN (Online) 2151-9617.
  5. Gbolagade K.A and Cotofana S.D. MRC Technique for RNS to Decimal Conversion for the moduli set {2n+2, 2n+1, 2n}. 16th Annual Workshop on Circuits, Systems and Signal Processing, pp.318-321, Veldhoven, The Netherlands, November 2008.
  6. Gbolagade K.A and Cotofana S.D.Residue-to-decimal converters for moduli set with common factors. 52nd IEEE International Midwest Symposium on Circuits and Systems (MINSCAS, 2009), PP.624-627, 2009.
  7. Narayanaswamy N. (2010). Optimization of New Chinese Remainder Theorems using special moduli sets.
  8. Narayanaswamy N., Skavantzos A., Stouraitis T. (2010). Optimal Modulus Sets for Efficient Residue-to-Binary Conversion Using the New Chinese Remainder Theorems. Accepted in 17th IEEE International Conference on Electronics, Circuits, and Systems, Athens.
  9. Number systems, IEEE Trans. on CAS -I, Vol. 41, No. 12, pp. 927-
  10. Omondi A and Premkumar B (2007).Residue Number System- Theory and Implementation (Volume 2)
  11. Szabo, N.S and Tanaka, R.I. (1967). Residue Arithmetic and Its Applications to Computer Technology. McGraw-Hill, New York.
  12. Umar A. F (2011) Data conversion in Residue Number System, Department of Electrical and Computer Engineering Mc Gill University Montreal.
  13. Wang, Y., Song, X., Aboulhamid, M., Shen, H. (2002). Adder based residue to binary number converters for (2n-1, 2n, 2n+1), IEEE Transactions on Signal Processing, vol.50, no.7, pp.1772-1779.
  14. I. R. Fadulilahi, E. K. Bankas, J. B. A. K. Ansuura (2015). Efficient Algorithm for RNS Implementation of RSA. International Journal of Computer Applications 11/2015; Vol.127, No.5, pp.14-19.

Keywords

Reverse Conversion, Optimization, Algorithm, Co-prime.