Высокоскоростной алгоритм определения знака числа в системе остаточных классов на основе функции ядра Акушского
https://doi.org/10.15514/ISPRAS-2026-38(3)-19
Аннотация
. В данной статье предлагается высокоскоростной алгоритм определения знака в системе остаточных классов на основе функции ядра Акушского. Метод использует набор модулей для эффективного определения знака числа. Ключевые преимущества включают в себя уменьшение размеров операндов и замену вычислительно сложных операций по модулю эффективными побитовыми операциями. Экспериментальные результаты показывают, что алгоритм на основе функции ядра Акушского, превосходит классические методы, достигая среднего ускорения в 25.6%. Алгоритм демонстрирует стабильную производительность во всех протестированных разрядностях, что делает его подходящим для приложений, требующих высокоскоростной арифметики системы остаточных классов, таких как цифровая обработка сигналов и криптография.
Ключевые слова
система остаточных классов,
высокопроизводительные вычисления,
функция ядра Акушского,
обнаружение знака.
При поддержке: Исследование выполнено за счет гранта Российского научного фонда № 25-71-30007.
Об авторах
Владислав Вячеславович ЛУЦЕНКО
Северо-Кавказский федеральный университет
Россия
Россия
Ассистент кафедры вычислительной математики и кибернетики факультета математики и компьютерных наук имени профессора Н.И. Червякова ФГАОУ ВПО «Северо-Кавказский федеральный университет». Сфера научных интересов: высокопроизводительные вычисления, система остаточных классов, умный город, нейронные сети, интернет вещей.
Айсанат Эдуардновна ГЕРЮГОВА
Северо-Кавказский федеральный университет
Россия
Россия
Студент кафедры математического анализа, алгебры и геометрии факультета математики и компьютерных наук имени профессора Н.И. Червякова ФГАОУ ВПО «Северо-Кавказский федеральный университет». Сфера научных интересов: система остаточных классов, математика и компьютерные науки.
Михаил Григорьевич БАБЕНКО
Северо-Кавказский федеральный университет
Россия
Россия
Доктор физико-математических наук, заведующий кафедры вычислительной математики и кибернетики факультета математики и компьютерных наук имени профессора Н.И. Червякова ФГАОУ ВПО «Северо-Кавказский федеральный университет». Сфера научных интересов: облачные вычисления, высокопроизводительные вычисления, система остаточных классов, нейронные сети, криптография.
Список литературы
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.
Рецензия
Для цитирования:
ЛУЦЕНКО В.В., ГЕРЮГОВА А.Э., БАБЕНКО М.Г. Высокоскоростной алгоритм определения знака числа в системе остаточных классов на основе функции ядра Акушского. Труды Института системного программирования РАН. 2026;38(3):15-32. https://doi.org/10.15514/ISPRAS-2026-38(3)-19
For citation:
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
Послать статью по эл. почте 