2025, випуск 1, c. 43-53
Одержано 10.02.2025; Виправлено 27.02.2025; Прийнято 25.03.2025
Надруковано 28.03.2025; Вперше Online 30.03.2025
https://doi.org/10.34229/2707-451X.25.1.4
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Піднесення до квадрату багаторозрядного числа на 8 процесорах у паралельній моделі обчислень
А.М. Терещенко 
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. На даний час безпека та конфіденційність даних стає нагальним викликом не тільки для приватних осіб, а і на державному рівні. Рівень кібератак виріс на стільки, що хакери можуть виводи з ладу сервери, змінювати дані в хмарних сховищах, що унеможливлює роботу цілих державних органів на тривалий період, що потребує значних зусиль на відновлення ресурсів. Кібератаки стають більш організованими та вибірковими. Використання асиметричних криптографічних програмно-апаратних комплексів стає обов’язковим елементом захисту. Швидкодія асиметричних криптографічних операцій таких, як шифрування, дешифрування, верифікації ключів, залежить від швидкодії операції піднесення до квадрату за модулем. Використовуючи швидкі методи, операція піднесення до квадрату числа довжиною N розрядів може бути виконана з меншою складністю ніж операція множення двох чисел довжиною N розрядів.
У даній роботі розглядається метод реалізації операції піднесення до квадрату, який дозволяє зменшити кількість операцій множення та піднесення до квадрату у порівнянні з методом Карацуби. Запропонований метод може бути використано рекурсивно, є зручним для розпаралелювання, що збільшує його діапазон ефективного використання.
Мета роботи. Зменшити кількість однорозрядних операцій множення та піднесення до квадрату для пришвидшення часу виконання операції піднесення до квадрату числа довжиною N розрядів (N=2n). Зменшити кількість множень довжиною N/4 розрядів до 8 операцій у разі піднесення до квадрату числа довжиною N розрядів. Зменшити загальну обчислювальну складність та знайти модифікацію, при якій кількість кроків додавання та віднімання буде найменшою у порівнянні з іншими модифікаціями. Побудувати алгоритм піднесення до квадрату на основі знайденої модифікації. Знайти ефективний метод піднесення до квадрату чисел довжиною до 4096 бітів з можливістю розпаралелення.
Результати. Розглянута структура числа, яке розбивається на чотири частини, для реалізації операції піднесення до квадрату. Досліджено вплив розділення 4-х розрядного числа на 2-х розрядне число та 4-х розрядне число з простішою структурою, штучно створеною за рахунок повторюваності його частин, на реалізацію операції піднесення до квадрату. Розроблено метод реалізації операції піднесення до квадрату 4-х розрядного числа за вісім однорозрядних множень, що на одне множення менше ніж у методі Карацуби, який виконується рекурсивно. Для отримання результату операції піднесення до квадрату використовуються лінійні комбінації результатів множення. У роботі наведена така модифікація реалізації, яка має невелику кількість операцій додавань та віднімань у лінійних комбінаціях. Наведено алгоритм на основі запропонованої модифікації, де показано, як 4-х розрядне число з різнорідною структурою може бути розділене на 2-х розрядне число та 4-х розрядне число з простішою структурою за рахунок повторюваності. Проведено аналіз складності за кількістю однорозрядних операцій множення в залежності від довжина числа N у разі рекурсивного використання алгоритму реалізації операції піднесення до квадрату для порівняння з методом Карацуби.
Висновки. У роботі наведено алгоритм реалізації операції піднесення до квадрату 4-х розрядного числа на основі восьми однорозрядних множень, три з яких є операціями піднесення до квадрату. На прикладі показана реалізація операції піднесення до квадрату 4-х розрядного числа з різнорідною структурою. Проведена оцінка складності запропонованого методу для чисел довжиною N розрядів та показано, що обчислення може бути виконано на основі трьох піднесень до квадрату чисел довжиною N/4 розрядів та п‘яти множень чисел довжиною N/4 розрядів. На основі порівняльного аналізу показано, що запропонований метод піднесення до квадрату кращий за метод Карацуби на 11 % для (N = 4) та до 16 % зі збільшенням N. Для перевірки результату обчислення реалізовано у вигляді алгоритму-програми SquaringNumber2aa на мові програмування APL. Метод може бути використано рекурсивно, що підвищує можливості з розпаралелювання реалізації операції піднесення до квадрату великих чисел, що збільшує його діапазон ефективного використання до 4096 бітів.
Ключові слова: багаторозрядна арифметика, багаторозрядне множення, багаторозрядне піднесення до квадрату, багаторозрядне піднесення до квадрату за модулем, асиметрична криптографія, паралельна модель обчислень.
Цитувати так: Терещенко А.М. Піднесення до квадрату багаторозрядного числа на 8 процесорах у паралельній моделі обчислень. Cybernetics and Computer Technologies. 2025. 1. С. 43–53. https://doi.org/10.34229/2707-451X.25.1.4
Список літератури
1. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978. Vol. 21, N 2. P. 120–126.
2. Задирака В.К., Кудин А.М. Построение программно-аппаратных комплексов арифметики сверхбольших чисел. Компьютерная математика. 2001. Т.1. С. 158–163.
3. Tereshchenko A., Zadiraka V. Algorithm for calculation the carry and borrow signs in multi-digit operations in the parallel computational model. International Journal of Computing. 2023. 22(1). P. 21–28. https://doi.org/10.47839/ijc.22.1.2875
4. Карацуба А.А., Офман Ю.П. Умножение многоразрядных чисел на автоматах. ДАН CCCP. 1962. 145 (2). С. 293–294. http://mi.mathnet.ru/dan26729
5. Cook S.A. On the Minimum Computation Time of Functions, 1966 PhD thesis, Harvard University Department of Mathematics. http://cr.yp.to/bib/1966/cook.html (звернення: 10.02.2025)
6. Schonhage A., Strassen V. Schnelle Multiplikation großen Zahlen. Computing. 1971. Vol. 7, No. 3–4. P. 281–292. https://www.scribd.com/doc/68857222/Schnelle-Multiplikation-gro%C3%9Fer-Zahlen
7. Анісімов А.В. Алгоритмічна теорія великих чисел. Модулярна арифметика великих чисел. Київ: Видавничий дім “Академперіодика”, 2001. 153 с. http://books.zntu.edu.ua/book_info.pl?id=21106
8. Задірака В., Олексюк О. Комп’ютерна арифметика багаторозрядних чисел: Наукове видання. Київ. 2003. 263 с.
9. Николайчук Я.М., Касянчук М.М., Якименко І.З., Івасьєв С.В. Ефективний метод модулярного множення в теоретико-числовому базисі Радемахера – Крестенсона. Вісник Національного університету "Львівська політехніка". Комп’ютерні системи та мережі. 2014. № 806. C. 195–199. http://nbuv.gov.ua/UJRN/VNULPKSM_2014_806_31
10. Хіміч О.М., Сидорук В.А. Використання мішаної розрядності у математичному моделюванні. Математичне та комп’ютерне моделювання. Серія: Фізико-математичні науки. 2019. Вип. 19. С. 180–187. http://mcm-math.kpnu.edu.ua/article/view/174244
11. Задірака В.К., Терещенко А.М. Комп’ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. Київ: Наук. думка, 2021. 136 с.
12. Tereshchenko A., Zadiraka V. Generating Big Numbers for Testing Multi-Digit Arithmetic Algorithms. Cybernetics and Computer Technologies. 2021. Iss. 2. P. 39–56. https://doi.org/10.34229/2707-451X.21.2.4
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна