Generating Compact Residue Number Systems Bases
https://doi.org/10.15514/ISPRAS-2025-37(5)-3
Abstract
Modern computational tasks involving large-number processing demand not only high precision but also significant operational speed. In this context, the residue number system provides an effective approach for parallel processing of large numbers, with applications in cryptography, signal processing, and artificial neural networks. The primary task in defining such a system is determining its basis. This paper presents an algorithm for generating compact residue number system bases based on the Diemitko theorem. The proposed algorithm generates bases 15.5% faster on average than Pseudo-Mersenne-based construction and 75.7% faster than the general filtering method. Comparative analysis demonstrates that using compact bases delivers an average 12% acceleration in modular operations compared to special moduli sets.
Keywords
residue number system,
high-performance computing,
special sets of moduli,
generation of prime numbers,
cryptography.
Supporting agencies: The research was supported by the Russian Science Foundation Grant No. 25-71-30007, https://rscf.ru/en/project/25-71-30007/.
About the Authors
Vladislav Vyacheslavovich LUTSENKO
North-Caucasus Federal University
Russian Federation
Russian Federation
Postgraduate student, Department of Computational Mathematics and Cybernetics, Faculty of Mathematics and Computer Science named after Professor N.I. Chervyakov, North Caucasus Federal University. Research interests: high-performance computing, residue number system, smart city, neural networks, Internet of Things.
Mikhail Grigoryevich BABENKO
North-Caucasus Federal University
Russian Federation
Russian Federation
Dr. Sci. (Phys.-Math.), Head of the Department of Computational Mathematics and Cybernetics, Faculty of Mathematics and Computer Science named after Professor N.I. Chervyakov, North Caucasus Federal University. His research interests include cloud computing, high-performance computing, residue number systems, neural networks, cryptography.
References
1. Sousa L. Nonconventional computer arithmetic circuits, systems and applications. IEEE Circuits Syst. Mag, 2021, vol. 21, no. 1, pp. 6-40.
2. Garner H.L. The residue number system. Papers presented at the the March 3-5, 1959, western joint computer conference. ACM, 1959, pp. 146–153.
3. Луценко В.В., Бабенко М.Г., Хамидов М.М. Высокоскоростной метод перевода чисел из системы остаточных классов в позиционную систему счисления. Труды ИСП РАН, том 36, вып. 4, 2024 г., стр. 117-132. DOI: 10.15514/ISPRAS-2024-36(4)-9. / Lutsenko V.V., Babenko M.G., Khamidov M.M. High speed method of conversion numbers from residue number system to positional notation. Proceedings of the Institute for System Programming of the RAS, 2024, vol. 36, issue 4, pp. 117-132 (in Russian). DOI: 10.15514/ISPRAS-2024-36(4)-9.
4. Луценко В.В., Бабенко М.Г., Черных А.Н., Лапина М.А. Оптимизация алгоритма деления чисел в системе остаточных классов на основе функции ядра Акушского. Труды ИСП РАН, том 35, вып. 5, стр. 157-168. DOI: 10.15514/ISPRAS-2022-35(5)-11. / Lutsenko V.V., Babenko M.G., Tchernykh A.N., Lapina M.A. Optimization of a number division algorithm in the residue number system based on the Akushsky core function. Proceedings of the Institute for System Programming of the RAS, 2023, vol. 35, issue 5, pp. 157-168 (in Russian). DOI: 10.15514/ISPRAS-2022-35(5)-11.
5. Shiriaev E. Kucherov N., Babenko M., Nazarov A. Fast operation of determining the sign of a number in rns using the akushsky core function. Computation, 2023, vol. 11, no. 7, pp. 124.
6. Cardarilli G. C., Nannarelli A., Re M. RNS applications in digital signal processing. Embedded Systems Design with Special Arithmetic and Number Systems, 2017, pp. 181-215.
7. Schoinianakis D. Residue arithmetic systems in cryptography: a survey on modern security applications. Journal of Cryptographic Engineering, 2020, vol. 10, no. 3, pp. 249-267.
8. Nakahara H., Sasao T. A High-speed Low-power Deep Neural Network on an FPGA based on the Nested RNS: Applied to an Object Detector. 2018 IEEE international symposium on circuits and systems (ISCAS). – IEEE, 2018, pp. 1-5.
9. Ananda Mohan P. V. RNS in Cryptography. Residue Number Systems: Theory and Applications. – Cham: Springer International Publishing, 2016, pp. 263-347.
10. Fournaris A. P., Papachristodoulou L., Sklavos N. Secure and efficient rns software implementation for elliptic curve cryptography. 2017 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW). – IEEE, 2017, pp. 86-93.
11. Fournaris A. P., Papachristodoulou L., Batina L., Sklavos N. Secure and efficient RNS approach for elliptic curve cryptography, 2016.
12. Zalekian A., Esmaeildoust M., Kaabi A. Efficient implementation of NTRU cryptography using residue number system. International Journal of Computer Applications, 2015, vol. 124, no. 7.
13. Bajard J. C., Kaihara M., Plantard T. Selected RNS bases for modular multiplication. 2009 19th IEEE Symposium on Computer Arithmetic. – IEEE, 2009, pp. 25-32.
14. Bajard J. C., Fukushima K., Plantard T., Sipasseuth A. Generating very large RNS bases. IEEE Transactions on Emerging Topics in Computing, 2022, vol. 10, no. 3, pp. 1289-1301.
15. Lutsenko V., Zgonnikov M. Investigation of Neural Network Methods for Error Detection and Correction in the Residue Number System. International Workshop on Advanced Information Security Management and Applications. – Cham: Springer Nature Switzerland, 2024, pp. 194-206.
16. Omondi A. R., Premkumar A. B. Residue number systems: theory and implementation. – World Scientific, 2007, vol. 2.
17. Skavantzos A., Abdallah M., Stouraitis T. Large dynamic range RNS systems and their residue to binary converters. Journal of Circuits, Systems, and Computers, 2007, vol. 16, no. 02, pp. 267-286.
18. Molahosseini A. S., Teymouri F., Navi K. A new four-modulus RNS to binary converter. Proceedings of 2010 IEEE International Symposium on Circuits and Systems. – IEEE, 2010, pp. 4161-4164.
19. Lutsenko V.V., Kravtsov M.D., Gorlachev D.E., Mirny N.M. Research of special sets of moduli of the residue number system. Proceedings of the Institute for System Programming of the RAS, 2025, vol. 35, no. 5, pp. 157-168 (in Russian).
20. Kawamura S., Koike M., Sano F., Shimbo A. Cox-rower architecture for fast parallel montgomery multiplication. Advances in Cryptology—EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium, May 14–18, 2000 Proceedings 19. Springer Berlin Heidelberg, 2000. pp. 523-538.
21. Diemitko N. Generating multiprecision integer with guaranted primality. Proc. of the SIFIP Int. Conf. on Comp. Sci., IFIP Security 88, Amsterdam, 19-21 May, 1988. pp. 1-8.
Supplementary files
Review
For citations:
LUTSENKO V.V., BABENKO M.G. Generating Compact Residue Number Systems Bases. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(5):43-52. https://doi.org/10.15514/ISPRAS-2025-37(5)-3
Email this article 