High Speed Algorithm for Number Sign Detection in Residue Number System Based on Akushsky Core Function
https://doi.org/10.15514/ISPRAS-2026-38(3)-19
Abstract
This paper proposes a high-speed algorithm for sign detection in the residue number system based on the Akushsky core function. The method utilizes a set of moduli {2^n-1,2^(n+1)-1,2^(n+a) } to efficiently determine the sign of a number. Key advantages include reduced operand sizes and replacement of costly modulo operations with efficient bitwise manipulations. Experimental results show that the Akushsky core function-based approach outperforms the traditional method, achieving an average speedup of 25.6%. The algorithm shows consistent performance across all tested bit widths, making it particularly suitable for applications requiring high-speed residue number system arithmetic, such as digital signal processing and cryptography.
Supporting agencies: The research was supported by the Russian Science Foundation Grant No. 25-71-30007.
About the Authors
Mikhail Grigoryevich LUTSENKO
North-Caucasus Federal University
Russian Federation
Russian Federation
Assistant professor, 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.
Aisanat Eduardnovna GERYUGOVA
North-Caucasus Federal University
Russian Federation
Russian Federation
Student in the Department of mathematical analysis, algebra and geometry, Faculty of mathematics and computer science named after Professor N.I. Chervyakov, North Caucasus Federal University. Her research interests include residue number systems, mathematics, and computer science.
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. Schoinianakis, D. Residue arithmetic systems in cryptography: a survey on modern security applications. Journal of Cryptographic Engineering 2020, 10, 249-267.
2. Cheon, J.H.; Han, K.; Kim, A.; Kim, M.; Song, Y. A full RNS variant of approximate homomorphic encryption. In Proceedings of the International Conference on Selected Areas in Cryptography. Springer, 2018, pp. 347-368.
3. Bajard, J.C.; Eynard, J. RNS Approach in Lattice-Based Cryptography. Embedded Systems Design with Special Arithmetic and Number Systems 2017, pp. 345-368.
4. Selvam, R.; Tyagi, A. Power side channel resistance of RNS secure logic. In Proceedings of the 2018 31st International Conference on VLSI Design and 2018 17th International Conference on Embedded Systems (VLSID). IEEE, 2018, pp. 143-148.
5. Kawamura, S.; Komano, Y.; Shimizu, H.; Osuka, S.; Fujimoto, D.; Hayashi, Y.; Imafuku, K. Efficient algorithms for sign detection in RNS using approximate reciprocals. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 2021, 104, 121-134.
6. Lutsenko, V.; Zgonnikov, M. Investigation of Neural Network Methods for Error Detection and Correction in the Residue Number System. In Proceedings of the International Workshop on Advanced Information Security Management and Applications. Springer, 2024, pp. 194-206.
7. 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, 36, 117-132.
8. Bajard, J.C.; Didier, L.S.; Kornerup, P. An RNS Montgomery modular multiplication algorithm. IEEE Transactions on Computers 339 1998, 47, 766-776.
9. Nozaki, H.; Motoyama, M.; Shimbo, A.; Kawamura, S. Implementation of RSA algorithm based on RNS Montgomery multiplication. In Proceedings of the InternationalWorkshop on Cryptographic Hardware and Embedded Systems. Springer, 2001, pp. 364-376.
10. Cardarilli, G.; Re, M.; Lojacono, R. RNS-to-binary conversion for efficient VLSI implementation. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 2002, 45, 667-669.
11. Babenko, M.; Deryabin, M.; Piestrak, S.J.; Patronik, P.; Chervyakov, N.; Tchernykh, A.; Avetisyan, A. RNS number comparator based on a modified diagonal function. Electronics 2020, 9, 1784.
12. Akushsky, I.Y.; Burtsev, V.M.; Pak, I.T. Calculation of the positional characteristic (core) of the non-positional code; Nauka, 1977; pp. 17-25.
Review
For citations:
LUTSENKO M.G., GERYUGOVA A.E., BABENKO M.G. High Speed Algorithm for Number Sign Detection in Residue Number System Based on Akushsky Core Function. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2026;38(3):15-32. https://doi.org/10.15514/ISPRAS-2026-38(3)-19
Email this article 