Оптимизация алгоритма деления чисел в системе остаточных классов на основе функции ядра Акушского
Владислав Вячеславович ЛУЦЕНКО,
Михаил Григорьевич БАБЕНКО,
Андрей Николаевич ЧЕРНЫХ,
Мария Анатольевна ЛАПИНА https://doi.org/10.15514/ISPRAS-2022-35(5)-11
Аннотация
Система остаточных классов широко применяются в криптографии, цифровой обработке сигналов, системах обработки изображений и других областях, где требуется выполнение операций деления. Однако, операция деления является наиболее сложной с точки зрения вычислений в системе остаточных классов. В статье представлен оптимизированный алгоритм деления, основанный на функции ядра Акушского. Показано, что предложенный алгоритм по скорости вычислений эффективней, чем классическое итерационное деление.
Ключевые слова
система остаточных классов,
функция ядра Акушского,
модулярная арифметика,
немодульные операции,
итерационное деление.
При поддержке: Исследование выполнено за счет гранта Российского научного фонда № 19-71-10033, https://rscf.ru/project/19-71-10033/.
Об авторах
Владислав Вячеславович ЛУЦЕНКО
Северо-Кавказский центр математических исследований, Северо-Кавказский федеральный университет
Россия
Россия
Аспирант, кафедры вычислительной математики и кибернетики факультета математики и компьютерных наук имени профессора Н.И. Червякова ФГАОУ ВПО «Северо-Кавказский федеральный университет». Сфера научных интересов: высокопроизводительные вычисления, система остаточных классов, умный город, нейронные сети, интернет вещей.
Михаил Григорьевич БАБЕНКО
Северо-Кавказский федеральный университет,
Институт системного программирования РАН им. В.П. Иванникова
Россия
Россия
Доктор физико-математических наук, заведующий кафедры вычислительной математики и кибернетики факультета математики и компьютерных наук имени профессора Н.И. Червякова ФГАОУ ВПО «Северо-Кавказский федеральный университет». Сфера научных интересов: облачные вычисления, высокопроизводительные вычисления, система остаточных классов, нейронные сети, криптография.
Андрей Николаевич ЧЕРНЫХ
Институт системного программирования РАН им. В.П. Иванникова,
Центр научных исследований и высшего образования Энсенада,
Мексика
Мексика
Получил степень кандидата наук в Институте точной механики и вычислительной техники РАН. В настоящее время он является профессором Центра научных исследований и высшего образования в Энсенаде, Нижняя Калифорния, Мексика. В научном плане его интересуют многоцелевая оптимизация распределения ресурсов в облачной среде, проблемы безопасности, планирования, эвристики и метаэвристики, энергосберегающие алгоритмы, интернет вещей.
Мария Анатольевна ЛАПИНА
Северо-Кавказский федеральный университет
Россия
Россия
Кандидат физико-математических наук, доцент, доцент кафедры информационной безопасности автоматизированных систем ФГАОУ ВО «Северо-Кавказский федеральный университет». Сфера научных интересов: цифровые технологии, управление информационной безопасностью, процессный подход, образовательный процесс, криптография.
Список литературы
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
Рецензия
Для цитирования:
ЛУЦЕНКО В.В., БАБЕНКО М.Г., ЧЕРНЫХ А.Н., ЛАПИНА М.А. Оптимизация алгоритма деления чисел в системе остаточных классов на основе функции ядра Акушского. Труды Института системного программирования РАН. 2023;35(5):157-168. https://doi.org/10.15514/ISPRAS-2022-35(5)-11
For citation:
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
Послать статью по эл. почте 