Optimization of a Number Division Algorithm in the Residue Number System Based on the Akushsky Core Function
Vladislav Vyacheslavovich LUTSENKO,
Mikhail Grigoryevich BABENKO,
Andrei TCHERNYKH,
Maria Anatolievna LAPINA https://doi.org/10.15514/ISPRAS-2022-35(5)-11
Abstract
Residue number systems find wide application in cryptography, digital and image signal processing, and other domains necessitating division operations. Nevertheless, division is the most computationally intensive activity in residue number systems. An optimized division algorithm based on the Akushsky core function is presented in this paper. The suggested method exhibits superior computational efficiency when compared to the conventional iterative division.
Keywords
residue number system,
Akushsky core function,
modular arithmetic,
non-modular operation,
iterative division.
Supporting agencies: The research was supported by the Russian Science Foundation Grant No. 19-71-10033, https://rscf.ru/en/project/19-71-10033/.
About the Authors
Vladislav Vyacheslavovich LUTSENKO
North-Caucasus Center for Mathematical Research, 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, Stavropol,
Ivannikov Institute for System Programming of the Russian Academy of Sciences
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.
Andrei TCHERNYKH
Институт системного программирования РАН им. В.П. Иванникова,
Центр научных исследований и высшего образования Энсенада,
Mexico
Mexico
Received his Cand. Sci. (Phys.-Math.) degree at the Institute of Precise Mechanics and Computer Engineering of the Russian Academy of Sciences. Now he is holding a full professor position in computer science at CICESE Research Center, Ensenada, Baja California, Mexico. He is interesting in grid and cloud research addressing multi-objective resource optimization, both, theoretical and experimental, security, uncertainty, scheduling, heuristics and meta-heuristics, adaptive resource allocation, energy-aware algorithms and Internet of Things.
Maria Anatolievna LAPINA
North-Caucasus Federal University, Stavropol
Russian Federation
Russian Federation
Cand. Sci. (Phys.-Math.), Associate Professor, Associate Professor of the Department of Information Security of Automated Systems of the North Caucasus Federal University. Research interests: digital technologies, information security management, process approach, educational process, cryptography.
References
1. Mohan P. V. A., Mohan P. V. A. Residue Number Systems. Cham, Switzerland: Birkhäuser, 2016. – pp. 16-24.
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. Kasianchuk, M. M., Yakymenko, I. Z., Nykolaychuk, Y. M. (2021). Symmetric cryptoalgorithms in the residue number system. Cybernetics and Systems Analysis, 57(2), 2021, pp. 329-336.
4. Tchernykh, A., Schwiegelsohn, U., Talbi, E. G., Babenko, M. (2019). Towards understanding uncertainty in cloud computing with risks of confidentiality, integrity, and availability. Journal of Computational Science, vol. 36, 2019, P. 100581.
5. Червяков, Н. И., Коляда, А. А., Ляхов, П. А., Бабенко, М. Г., Лавриненко, И. Н., Лавриненко, А. В. Модулярная арифметика и ее приложения в инфокоммуникационных технологиях. М.: ФИЗМАТЛИТ, 2017, 440 c. / Chervyakov, N. I., Kolyada, A. A., Lyakhov, P. A., Babenko, M. G., Lavrinenko, I. N., Lavrinenko, A. V. Modular arithmetic and its applications in info-communication technologies. Moscow: Fizmatlit, 2017, 440 p. (in Russian).
6. Molahosseini A. S., Sorouri S., Zarandi A. A. E. Research challenges in next-generation residue number system architectures. Computer Science & Education (ICCSE), 7th International Conference, 2012, pp. 1658–1661.
7. Червяков Н.И., Ляхов П.А., Оразаев А.Р. Компьютерная оптика, том. 42, вып. 4, 2018 г., стр. 667-678: DOI: 10.18287/2412-6179-2018-42-4-667-678./ Chervyakov N.I., Lyakhov P.A., Orazaev A.R. Computer Optics, 2018, vol. 42, issue 4, pp. 667-678 (in Russian). DOI: 10.18287/2412-6179-2018-42-4-667-678.
8. Червяков Н.И., Лавриненко И. Н. Модулярные методы и алгоритмы деления на основе спуска Ферма и итераций Ньютона. Инфокоммуникационные технологии, том. 7, вып. 4, 2009 г., стр. 9–12. / Chervyakov N.I., Lavrinenko I.N. Modular methods and algorithms of division based on Fermat's descent and Newton's iterations. Info-communication Technologies, 2009, vol. 7, issue 4, pp. 9-12 (in Russian).
9. Червяков Н.И. Методы, алгоритмы и техническая реализация основных проблемных операций, выполняемых в системе остаточных классов. Инфокоммуникационные технологии, том. 9, вып. 4, 2011 г., стр. 4–12. / Cherviakov N.I. Methods, algorithms and technical implementation of the main problem operations performed in the residual class system. Info-communication Technologies, 2011, vol. 9, issue 4, pp. 4-12 (in Russian).
10. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М., Советское радио, 1968, 440 c. / Akushsky I. Ya., Yuditsky D. I. Computer arithmetic in residual classes. Moscow, Soviet Radio, 1968, 440 p. (in Russian).
11. Акушский И. Я., Бурцев В. М., Пак И. Т. О новой позиционной характеристике непозиционного кода и ее приложении. Теория кодирования и оптимизация сложных систем. Алма-Ата, Наука, КазССР, 1977, стр. 8–16. / Akushsky, I.Y., Burtsev, V.M., Pak, I.T. (1977) About the New Positional Characteristic of the Non-Positional Code and Its Application. In Theory of Coding and Optimization of Complex Systems, Alma-Ata, Nauka, KazSSR, 1977, pp. 8–16 (in Russian).
12. Shiriaev, E., Kucherov, N., Babenko, M., Lutsenko, V., Al-Galda, S. Algorithm for Determining the Optimal Weights for the Akushsky Core Function with an Approximate Rank. Applied Sciences, 13(18), 2023, 10495. https://doi.org/10.3390/app131810495.
13. Акушский И. Я., Бурцев В. М., Пак И. Т. Алгоритмы деления с использованием ядерной характеристики. Теория кодирования и оптимизация сложных систем. Алма-Ата, Наука, КазССР, 1977, стр. 26–33. / Akushsky, I.Y., Burtsev, V.M., Pak, I.T. (1977) Division Algorithms Using Core Characteristics. In Theory of Coding and Optimization of Complex Systems, Alma-Ata, Nauka, KazSSR, 1977, pp. 26–33 (in Russian).
14. Diffie W., Hellman M. E. New Directions in Cryptography. IEEE Transactions on Information Theory, 22(18), pp. 644–654. doi:10.1109/TIT.1976.1055638
Review
For citations:
LUTSENKO V.V., BABENKO M.G., TCHERNYKH A., 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 (Proceedings of ISP RAS). 2023;35(5):157-168. (In Russ.) https://doi.org/10.15514/ISPRAS-2022-35(5)-11
Email this article 