Efficient Number Comparison in the Residue Number System based on Positional Characteristics
Mikhail Grigorievitch Babenko,
Andrei Tchernykh,
Nikolay Ivanovitch Chervyakov,
Viktor Andreevich Kuchukov,
Vanessa Miranda-Lopes,
Raúl Rivera Rodriguez,
Zhihui Du https://doi.org/10.15514/ISPRAS-2019-31(2)-13
Abstract
An important operation for data processing is a number comparison. In Residue Number System (RNS), it consists of two steps: the computation of the positional characteristic of the number in RNS representation and comparison of its positional characteristics in the positional number system. In this paper, we propose a new efficient method to compute the positional characteristic based on the approximate method. The approximate method as a tool to compare numbers does not require resource-consuming non-modular operations that are replaced by fast bit right shift operations and taking the least significant bits. We prove that in case when the dynamic range of RNS is an odd number, the size of the operands is reduced by the size of the module. If one of the RNS moduli is a power of two, then the size of the operands is less than the dynamic range. It makes our method efficient for hardware implementation of cryptographic primitives and digital signal processing.
Supporting agencies: Scholarship of the President of the Russian Federation to young scientists and graduate students, RFBR
About the Authors
Mikhail Grigorievitch Babenko
North Caucasus Federal University
Russian Federation
Lecturer of the Department of Applied Mathematics and Mathematical Modeling of the North Caucasus Federal University
Russian Federation
Lecturer of the Department of Applied Mathematics and Mathematical Modeling of the North Caucasus Federal University
Andrei Tchernykh
CICESE Research Center, Ensenada
Mexico
Full professor in computer science at CICESE Research Center
Mexico
Full professor in computer science at CICESE Research Center
Nikolay Ivanovitch Chervyakov
North Caucasus Federal University
Russian Federation
Doctor of Technical Sciences, Professor, Head of the Department of Applied Mathematics and Computer Science of the North Caucasus Federal University
Russian Federation
Doctor of Technical Sciences, Professor, Head of the Department of Applied Mathematics and Computer Science of the North Caucasus Federal University
Viktor Andreevich Kuchukov
North Caucasus Federal University
Russian Federation
Specialist of the department of scientific and technical information, scientometrics and export control of the Department of Science and Technology of the North Caucasus Federal University
Russian Federation
Specialist of the department of scientific and technical information, scientometrics and export control of the Department of Science and Technology of the North Caucasus Federal University
Vanessa Miranda-Lopes
CICESE Research Center
Mexico
Mexico
Raúl Rivera Rodriguez
CICESE Research Center
Mexico
Mexico
Zhihui Du
Tsinghua University
China
Associate professor at the Department of Computer Science and Technology of Tsinghua University
China
Associate professor at the Department of Computer Science and Technology of Tsinghua University
References
1. Chang C.H., Molahosseini A.S., Zarandi A.A.E., Tay T.F. Residue number systems: A new paradigm to datapath optimization for low-power and high-performance digital signal processing applications. IEEE circuits and systems magazine, vol. 15? № 4, 2015, pp. 26-44.
2. Chervyakov N., Babenko M., Tchernykh A., Kucherov N., Miranda-López V., Cortés-Mendoza J. M. AR-RRNS: Configurable reliable distributed data storage systems for Internet of Things to ensure security. Future Generation Computer Systems, vol. 92, 2019, pp. 1080-1092.
3. Sousa L., Antao S., Martins P. Combining residue arithmetic to design efficient cryptographic circuits and systems. IEEE Circuits and Systems Magazine, vol. 16, № 4, 2016, pp. 6-32.
4. Chervyakov N.I., Lyakhov P.A., Babenko M. Digital filtering of images in a residue number system using finite-field wavelets. Automatic Control and Computer Sciences, vol. 48, № 3, 2014, pp. 180-189.
5. Ye R., Boukerche A., Wang H., Zhou X., Yan B. RESIDENT: a reliable residue number system-based data transmission mechanism for wireless sensor networks. Wireless Networks, vol. 24, № 2, 2018, pp. 597-610.
6. Tchernykh A., Schwiegelsohn U., Talbi E. G., Babenko M. Towards understanding uncertainty in cloud computing with risks of confidentiality, integrity, and availability. Journal of Computational Science, 2016 (in Press), DOI: 10.1016/j.jocs.2016.11.011.
7. Miranda-López V., Tchernykh A., Cortés-Mendoza J.M., Babenko M., Radchenko G., Nesmachnow S., Du Z. Experimental Analysis of Secret Sharing Schemes for Cloud Storage Based on RNS. In Proc. of the Latin American High Performance Computing Conference, 2017, pp. 370-383.
8. Tchernykh A., Babenko M., Chervyakov N., Cortés-Mendoza J. M., Kucherov N., Miranda-López V., Deryabin M., Dvoryaninova I., Radchenko G. Towards mitigating uncertainty of data security breaches and collusion in cloud computing. In Proc. of the 28th International Workshop on Database and Expert Systems Applications (DEXA), 2017, pp. 137-141.
9. Babenko M., Chervyakov N., Tchernykh A., Kucherov N., Shabalina M., Vashchenko I., Radchenko G., & Murga D. Unfairness correction in P2P grids based on residue number system of a special form. In Proc. of the 28th International Workshop on Database and Expert Systems Applications (DEXA), 2017, pp. 147-151.
10. Szabo N.S., Tanaka R.I. Residue arithmetic and its applications to computer technology. N.Y., McGraw-Hill, 1967, 236 p.
11. Bi S., Gross W.J. The mixed-radix Chinese remainder theorem and its applications to residue comparison. IEEE Transactions on Computers, vol. 57. № 12, 2008, pp. 1624-1632.
12. Wang Y. Residue-to-binary converters based on new Chinese remainder theorems. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 47, № 3, 2000, pp. 197-205.
13. Dimauro G., Impedovo S., Pirlo G. A new technique for fast number comparison in the residue number system. IEEE transactions on computers, vol. 42, № 5, 1993, pp. 608-612.
14. Burgess N. Scaling an RNS number using the core function. In Proc. of the 16th IEEE Symposium on Computer Arithmetic, 2003. pp. 262-269.
15. Dimauro G., Impedovo S., Modugno R., Pirlo G., Stefanelli R. Residue-to-binary conversion by the" quotient function". IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. vol. 50. № 8, 2003, pp. 488-493.
16. Pirlo G., Impedovo D. A new class of monotone functions of the residue number system. International Journal of Mathematical Models and Methods in Applied Sciences, vol. 7. № 9, 2013, pp. 803-809.
17. Chervyakov N.I., Molahosseini A.S., Lyakhov P.A., Babenko M.G., Deryabin M.A. Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem. International Journal of Computer Mathematics, vol. 94. № 9, 2017, pp.1833-1849.
18. Patronik P., Piestrak S.J. Design of Reverse Converters for General RNS Moduli Sets {2^k,2^n-1,2^n+ 1,2^(n+ 1)-1} and {2^k,2^n-1,2^n+ 1,2^(n-1)-1} (n even). IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 61, № 6, 2014, pp.1687-1700.
19. Phatak D.S., Houston S.D. New distributed algorithms for fast sign detection in residue number systems (RNS). Journal of Parallel and Distributed Computing, vol. 97, issue C, 2016, pp. 78-95.
20. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М., Советское радио, 1968, 440 c. / Akushsky I. Ya., Yuditsky D. I. Computer arithmetic in residual classes. Moscow, Soviet Radio, 1968, 440 p. (in Russian).
21. Omondi A.R., Premkumar B. Residue number systems: theory and implementation. L., Imperial College Press, 2007, 296 p.
22. Isupov K. An Algorithm for Magnitude Comparison in RNS based on Mixed-Radix Conversion II. International Journal of Computer Applications, vol. 141, № 5, 2016.
23. Van Vu T. Efficient implementations of the Chinese remainder theorem for sign detection and residue decoding. IEEE Transactions on Computers, vol. 100, № 7, 1985, pp. 646-651.
24. Mohan P.A. RNS to binary conversion using diagonal function and Pirlo and Impedovo monotonic function. Circuits, Systems, and Signal Processing, vol. 35, № 3, 2016, pp. 1063-1076.
Review
For citations:
Babenko M.G., Tchernykh A., Chervyakov N.I., Kuchukov V.A., Miranda-Lopes V., Rivera Rodriguez R., Du Zh. Efficient Number Comparison in the Residue Number System based on Positional Characteristics. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(2):187-201. (In Russ.) https://doi.org/10.15514/ISPRAS-2019-31(2)-13
Email this article 